Lawrencenko, Serge A short treatise of spinal quadrangulations. (English) Zbl 1257.05072 J. Commun. Comput. 9, No. 10, 1124-1129 (2012). This article introduces a new method, called the spinal method, for generating quadrangulations of closed orientable surfaces with given properties. Those surfaces arise as the thickenings of certain spatial graphs called the spines. The properties of spinal quadrangulations are determined by their spines. The proposed method is found to be handier compared to the method of current graphs which was previously used. Many new minimal (with respect to the number of vertices, or faces) quadrangulations with given genus are discovered, in addition to the ones already found by N. Hartsfield and G. Ringel [J. Comb. Theory, Ser. B 46, No. 1, 84–95 (1989; Zbl 0665.05006)]. A new homology formula is obtained as a byproduct. A curved \(d\)-polyhedron \(|K|\) is the (non-PL) embedded image in \(\mathbb{R}^n\) of a simplicial complex \(K\) with dimension \(d \leq n-1.\) Let \(N^n (|K|)\) denote a closed regular neighborhood of \(|K|\) and let \(\beta_k (|K|)\) designates the \(k\)-th Betti number of \(|K|.\) The following formula is provided with rational coefficients for each integer \(k\) (\(0 \leq k \leq n-1)\): \(\beta_k (\partial N^n (|K|)) = \beta_k (|K|) + \beta_{n-k-1}(|K|)\). Another byproduct is the following optimization result: The maximum chromatic number \(n\) of a graph with first Betti number not exceeding a given value \(g\) is attained by the largest complete graph \(K_n\) with \(\beta_1 (K_n) \leq g\). Reviewer: Serge Lawrencenko (Moskva) Cited in 2 Reviews MSC: 05C35 Extremal problems in graph theory 05C10 Planar graphs; geometric and topological aspects of graph theory 05C15 Coloring of graphs and hypergraphs 90C27 Combinatorial optimization 57Q40 Regular neighborhoods in PL-topology 57M15 Relations of low-dimensional topology with graph theory 52B70 Polyhedral manifolds Keywords:embedding of graph; quadrangulation of surface; chromatic number; curved polyhedron; regular neighborhood; homology; Betti number; computer animation; spinal method Citations:Zbl 0665.05006 PDFBibTeX XMLCite \textit{S. Lawrencenko}, J. Commun. Comput. 9, No. 10, 1124--1129 (2012; Zbl 1257.05072)