ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 9 (2015) 145-149
Construction of planar 4-connected triangulations
Gunnar Brinkmann
Applied Mathematics, Computer Science and Statistics, Ghent University, Krijgslaan 281 S9, 9000 Ghent, Belgium
Craig Larson
Department of Mathematics and Applied Mathematics, Virginia Commonwealth University, 4106 Grace E. Harris Hall, 1015 Floyd Avenue, Richmond, VA 23284-2014
Jasper Souffriau
Applied Mathematics, Computer Science and Statistics, Ghent University, Krijgslaan 281 S9, 9000 Ghent, Belgium
Nico Van Cleemput
Applied Mathematics, Computer Science and Statistics, Ghent University, Krijgslaan 281 S9, 9000 Ghent, Belgium
Received 20 March 2013, accepted 14 August 2013, published online 21 November 2014
In this article we describe a recursive structure for the class of 4-connected triangulations or - equivalently - cyclically 4-connected plane cubic graphs.
Keywords: Planar triangulation, cubic graph, generation, recursive structure. Math. Subj. Class.: 05C10, 05C30, 05C75
Introduction
A recursive structure for a class C of graphs is a base set B c C of initial graphs together with a set of operations on graphs that transform a graph in C to another graph in C so that each graph in C can be constructed from a graph in B by a sequence of these operations.
E-mail addresses: Gunnar.Brinkmann@UGent.be (Gunnar Brinkmann), clarson@vcu.edu (Craig Larson), Jasper.Souffriau@UGent.be (Jasper Souffriau), Nicolas.VanCleemput@UGent.be (Nico Van Cleemput)
Abstract
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
146
Ars Math. Contemp. 9 (2015) 151-163
An operation is typically the replacement of a finite substructure by another - larger -substructure. In the ideal case, the set B as well as the set of operations are finite and small. All graphs discussed in this article are simple.
The two main applications for recursive structures are structure generation programs and inductive proofs, where the recursive structures describe the induction step. In this paper we discuss planar triangulations - that is plane graphs where every face is a triangle. For several classes of triangulations, recursive structures have been published: for all triangulations (that is: 3-connected triangulations) [6], for 5-connected triangulations [1][5], for triangulations with minimum degree 4 [2], for 3- and 4- connected triangulations with minimum degree 5 [3], and for Eulerian triangulations [2]. In the dual, these are constructions for 3-connected planar cubic graphs, cyclically 5-connected planar cubic graphs,
3-connected	planar cubic graphs with girth 4, 3- resp. cyclically 4-connected planar cubic graphs with girth 5 and 3-connected bipartite planar cubic graphs.
In this article we will add the missing link between 3-connected triangulations and 5-connected triangulations and give a recursive structure for 4-connected triangulations. The operations necessary to construct all 4-connected triangulations are in fact the same as the ones used in [4] to construct all triangulations with minimum degree 4 - except for the operation inducing separating triangles. While it is obvious that an operation introducing separating triangles does not lead to 4-connected triangulations, it is not obvious that all
4-connected	triangulations can be obtained with the remaining two operations.
□
O5
4	5
e
Figure 1: Two of the operations used by Eberhard [6] to generate all triangulations. Edges and vertices outside of the bounding 4-, or 5-cycle in the figure are not drawn.
Two of the operations given by Eberhard to construct all triangulations are given in Figure 1. We will show:
Theorem 0.1. The class C4 of all 4-connected triangulations can be generated from the octahedron graph (depicted in Figure 2) by operations O4 and O5.
O
G. Brinkmann et al.: Construction of planar 4-connected triangulations	147
Proof. We will write C4 for the class C4 without the octahedron graph.
The operations O4 and O5 are in fact similar to special cases of the edge expansion operation used by Batagelj in [2]. This can best be seen when looking at the reduction -that is the inverse of the construction operation. If one compresses the edges marked with an x (that is: removes the edge and identifies the endpoints) in Figure 1, the resulting graph is the same as after replacing the vertices and their adjacent edges by one, resp. two edges.
To prove this theorem, note first that in a triangulation being 4-connected is equivalent to not having a separating - that is: non-facial - 3-cycle. We will show that for each element of the class C4 an inverse operation can be applied that does not introduce separating 3-cycles and therefore leads to an element of C4. This is the consequence of 3 observations;
(a)	In a 4-connected triangulation no two edges in the same facial triangle belong to the
same separating 4-cycle.
This follows immediately as in that case the other edges of the separating 4-cycle together with the third edge of the triangle would form a separating 3-cycle.
(b)	In a 4-connected triangulation that is not the octahedron graph, no two edges in the
same facial triangle with a common vertex v of degree 4 belong to different separating 4-cycles C, C'.
Suppose that this was the case. Then - due to (a) - the two separating 4-cycles must cross each other and there is an edge {v, y1} belonging to (w.l.o.g.) C so that the next edges {v, x1}, {v, x2} in counterclockwise, resp. clockwise direction around v belong to the separating 4-cycle C' formed by the vertices x1, v, x2, a. This situation is depicted in Figure 3.
From the previous observation it follows that C cannot contain x1 or x2, so the Jordan curve theorem gives that it must contain a and that the situation is as with the dotted edges in Figure 3. This implies the presence of 8 triangles which must all be facial triangles - as no non-facial triangles exist - and implies that there are no more edges than those depicted. So the graph was the octahedron graph.
(c)	In a 4-connected triangulation without vertices of degree 4, for each edge {v, x1} con-
taining a vertex v of degree 5 that belongs to a separating 4-cycle C, either the previous or the next edge in the cyclic order around v or both do not belong to a separating 4-cycle.
148
Ars Math. Contemp. 9 (2015) 151-163
a
x
2
Figure 3: Two separating 4-cycles crossing in a vertex of degree 4.
By choosing the neighboring edge as the one that shares a triangle with both edges of C containing v, we can follow the same line of arguments as before to get - up to symmetry -the situation in Figure 4. In this case we don't have 8 triangles, but we do have the triangles
(a, yi,x2), (xi, yi,a), (v,yi,xi) and (x2,yi,v) which must all be facial. This implies that the degree of yi is 4 - contradicting the assumption.
Figure 4: Two separating 4-cycles crossing in a vertex of degree 5 in a triangulation with minimum degree 5.
As in a 4-connected triangulation there are always vertices with degree 4 or degree 5, (a),(b),(c) together imply that a triangulation in C4 contains an edge adjacent to a vertex of degree 4 or 5 that does not lie on a separating 4-cycle. Using this edge as the edge x in Figure 1 we can reduce such a triangulation to a smaller one without separating triangles.
a
□
References
[1] D. Barnette, On generating planar graphs, Discrete Math. 7 (1974), 199-208.
G. Brinkmann et al.: Construction of planar 4-connected triangulations
149
[2]	V. Batagelj, An improved inductive definition of two restricted classes of triangulations of the plane, Combinatorics and Graph Theory, Banach Center Publications 25 (1989), 11-18.
[3]	G. Brinkmann and B. D. McKay, Construction of planar triangulations with minimum degree 5, Discrete Math 301 (2005), 147-163.
[4]	G. Brinkmann and B. D. McKay, Fast generation of planar graphs, MATCH Commun. Math. Comput. Chem. 58 (2007), 323-357, see http://cs.anu.edu.au/~bdm/index.html.
[5]	J. W. Butler, A generation procedure for the simple 3-polytopes with cyclically 5-connected graphs, Can. J. Math. 26 (1974), 686-708.
[6]	V. Eberhard, Zur Morphologie der Polyeder. Teubner, 1891.