ARS MATHEMATICA CONTEMPORANEA Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 8 (2015) 337-363 Alternating plane graphs Ingo Althöfer Department of Mathematics and Computer Science, Friedrich-Schiller Universität, Ernst-Abbe-Platz 2, 07743 Jena - Germany Jan Kristian Haugland Arnstein Arnebergs vei 30, leilighet 308, 1366 Lysaker, Norway Department of Applied Mathematics, Computer Science and Statistics, Ghent University, Krijgslaan 281 - S9 - WE02, 9000 Ghent, Belgium Department of Mathematics and European Centre of Excellence NTIS (New Technologies for the Information Society), University of West Bohemia, Univerzitni 8, 30614 Pilsen, Czech Republic Received 17 December 2013, accepted 20 February 2015, published online 29 May 2015 A plane graph is called alternating if all adjacent vertices have different degrees, and all neighboring faces as well. Alternating plane graphs were introduced in 2008. This paper presents the previous research on alternating plane graphs. There are two smallest alternating plane graphs, having 17 vertices and 17 faces each. There is no alternating plane graph with 18 vertices, but alternating plane graphs exist for all cardinalities from 19 on. From a small set of initial building blocks, alternating plane graphs can be constructed for all large cardinalities. Many of the small alternating plane graphs have been found with extensive computer help. Theoretical results on alternating plane graphs are included where all degrees have to be from the set {3,4,5}. In addition, several classes of "weak alternating plane graphs" (with vertices of degree 2) are presented. * Corresponding author. Supported by the project NEXLIZ CZ.1.07/2.3.00/30.0038, which is co-financed by the European Social Fund and the state budget of the Czech republic. Karl Scherer 11 Utting Street, Birkdale, 0626 Auckland, New Zealand Frank Schneider Dr.-Bernhard-Klein-Straße 99, 52078 Aachen, Germany Nico Van Cleemput * 4= Abstract ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/ 338 Ars Math. Contemp. 8 (2015) 235-244 4 3 5 4 1 2 5 1 3 6 2 5 3 2 1 5 2 4 1 4 3 Figure 1: Karl Scherer: Squaring the square with 21 alternating squares. Keywords: Plane graph, alternating degrees, exhaustive search, heuristic search. Math. Subj. Class.: 05C10, 05C75 1 Introduction The concept of alternating plane graphs was introduced by I. Althofer in January 2008. Years before, he had seen K. Scherer's squarings of a square, in particular the nice symmetric one where 21 small squares exactly fill a square of side length 16 in such a way that no two squares with the same side length join an edge or a vertex (see Figure 1). Scherer called such arrangements "alternating tilings". The 21-solution is the second smallest such object. This concept of alternating tilings formed the inspiration for the definition of alternating plane graphs. A large portion of the history of the development of this concept can be found at [8]. The paper is organized as follows. In Section 2 we give the necessary definitions. In Section 3 several theorems about different types of alternating plane graphs are proven. In Section 4 and Section 5 we describe exhaustive and heuristic searches for alternating plane graphs. Section 6 gives an overview of the alternating plane graphs constructed by hand and by these searches. Section 7 and Section 8 deal with several techniques to construct large alternating plane graphs. In Section 9 we describe a relaxation of the definition of alternating plane graphs. E-mail addresses: ingo.althoefer@uni-jena.de (Ingo Althofer), admin@neutreeko.net (Jan Kristian Haugland), karlscherer3@yahoo.co.nz (Karl Scherer), hobblefrank@t-online.de (Frank Schneider), nico.vancleemput@gmail.com (Nico Van Cleemput) I. Althofer et al.: Alternating plane graphs 339 2 Definition Note that a planar graph is a graph that can be embedded in the plane without crossing edges. A plane graph is a particular embedding of a planar graph. Definition 2.1. A plane graph is called an alternating plane graph, when the following conditions are fulfilled: • There are no adjacent vertices with the same degree. • There are no adjacent faces with the same size. • Each vertex has degree at least 3. • Each face has size at least 3. Note that the exterior face is also considered to be a face and also needs to satisfy the conditions above. The following lemma follows immediately from the definition. Lemma 2.2. If G is a 3-edge-connected alternating plane graph, then the dual of G is also an alternating plane graph. For a 2-edge-connected alternating plane graph that is not 3-edge-connected, the dual is not a simple graph, and therefore the dual is not an alternating plane graph. Note that an alternating plane graph is always at least 2-edge-connected, since plane graph with edge connectivity 1 contains a face that is adjacent to itself. 3 Theoretical results Definition 3.1. An alternating plane graph is called an (xi,..., xn)-alternating plane graph if all vertices have degree x1,..., xn-1 or xn and all faces have x1,..., xn-1 or xn sides. 3.1 Results for (3,4, 5)-alternating plane graphs Let v denote the number of vertices of degree i, and let f denote the number of faces with j sides. Theorem 3.2. If G is a (3,4, 5)-alternating plane graph, then v3 = f3, v4 = f4 and V5 = f5. Proof. Suppose G is a (3,4,5)-alternating plane graph. Summing the edges over the vertices shows that the total number of edges equals 3v3+4V4+5v5, while summing over the faces shows that it is 3f3 +4f4+5f5. So we have 2 > VV AAAAW O 14AAAAAAAAA£, VJ V WA U1V 1UVVO OllV W O H1UI Al. AO ^ 3v3 + 4v4 + 5v5 = 3fs + 4f4 + 5f5 2 2 Euler's formula gives (3.1) Ot . -U uo/fxfxfl 3V3 + 4V4 + 5V5 , 3fs + 4f4 + 5f5 2(V3 + V4 + V5 ) + 2(f3 + f4 + f5) = -2--1--2--+ 4 which simplifies to V3 + f3 = V5 + f5 + 8 (3.2) 340 Ars Math. Contemp. 8 (2015) 235-244 The rest of the proof is based on counting (i, j)-combinations, that is, the number of instances of a vertex of degree i incident with a face with j sides. For example, each vertex of degree 3 must be incident with a triangle, a quadrilateral and a pentagon, and each triangle must be incident with one vertex of each degree (3, 4 and 5). So we see that the number of (3, 3)-combinations must be equal to v3, but it must also be equal to /3, so we can deduce that V3 = /3 (3.3) Note that (3.1) and (3.3) together implies that v5 - /5 must be divisible by 4. Due to parity, each pentagon is incident with at least one vertex of each degree too, while a quadrilateral might have just two values represented. Counting (3, 5)-combinations shows that /5 < V3 (3.4) while a dual argument (counting (5, 3)-combinations) shows that V5 < /3 (3.5) Combining (3.1), (3.2), (3.3), (3.4) and (3.5) gives us five possibilities: v5 = v3 — 8, /5 = v3 v5 = v3 — 6, /5 = v3 —2 v5 = v3 — 4, /5 = v3 —4 v5 = v3 — 2, /5 = v3 —6 v5 = v3, /5 = v3 —8 Let a denote the number of vertices of degree 5 incident with exactly one face with i sides (and two of each of the other two types). Adding these up gives the total number of vertices of degree 5; i.e., a3 + a4 + a5 = v5. Since a vertex of degree 5 is incident with either 1 or 2 triangles, the number of (5,3)-combinations is a3 + 2a4 + 2a5, and since each triangle is incident with exactly one vertex of degree 5, we have a3 + 2a4 + 2a5 = /3 = v3. Thus, a3 = 2v5 — v3 and a4 + a5 = v3 — v5. It follows that 0 < a5 < V3 — V5 (3.6) Similarly, with bj denoting the number of pentagons incident with exactly one vertex of degree j, a dual argument shows that b3 = 2/5 — v3 and b4 + b5 = v3 — /5, and it follows that 0 < b5 < v3 — /5 (3.7) The number of (5,5)-combinations is 2a3 + 2a4 + a5 = a5 + 2(v5 — a5) = 2v5 — a5, and a dual argument shows that it is also equal to 2/5 — b5. So we have a5 — b5 = 2(v5 — /5) (3.8) Now let us inspect the possible values of v5 and /5 found earlier in view of (3.6), (3.7) and (3.8): I. Althofer et al.: Alternating plane graphs 341 V5 /5 2(v5 - /5) V3 - 8 V3 65 =0 -16 V3 - 6 V3 - 2 65 < 2 -8 V3 - 4 V3 - 4 0 V3 - 2 V3 - 6 0,5 < 2 8 V3 V3 - 8 0,5 =0 16 Since o5 and 65 are both non-negative integers, it is clear that (3.8) is only possible if V5 = /5 = V3 - 4. Of course, (3.1) now also gives v4 = /4 and the proof is complete. □ We can go a little bit further and show that if p(i, j) denotes the number of (i, j)-combinations, then p(i, j) = p(j, i) for all i,j in {3,4, 5}. We have p(3,j) = v3 and p(i, 3) = /3 for each i, j, and we know that v3 = /3. So it remains to prove that p(4, 5) = p(5,4). But p(4,5) = 263 + 64 + 265 andp(5,4) = 2a3 + a4 + 2a5, so it suffices to verify that a = 6j for every i, and this is immediate from the proof of the theorem. Corollary 3.3. There is no (3,4, 5) -alternating graph with fewer than 17 vertices. Proof. Let r = v3 = /3. So there are r vertices of degree 3, r - 8 vertices incident with a triangle, two quadrilaterals and two pentagons, and 4 other vertices of degree 5, and correspondingly for the dual objects. An immediate consequence is that r is at least 8. The number of edges incident with a triangle is 3r. In addition, each of the r vertices of degree 3 is incident with an edge that is not incident with any triangles. The r edges thus obtained are all distinct, since each one is only incident with one vertex of degree 3. Hence, there are at least 4r > 32 edges, and the result then follows from Euler's formula. □ For larger r, we can get a better estimate for the number of edges than 4r by considering pentagons instead. There are r - 4 pentagons, contributing 5r - 20 edges, and as above, r distinct edges incident with a triangle, a quadrilateral, and a vertex of degree 3. This gives a lower bound of 6r - 20 edges. Any edges not counted so far must be incident with a triangle, a quadrilateral and two vertices of degrees 4 and 5. The number of such edges is bounded by the number of triangles, which gives an upper bound of 7r - 20 edges in total. Furthermore, since we have that the number of edges is 3/3 + 4/4 + 5/5 2 , it follows that the number of quadrilaterals is in the interval [r - 5, §r - 5]. 3.2 X, Y-alternating plane graphs Definition 3.4. An alternating plane graph is called an X, Y-alternating plane graph if there are exactly X different vertex degrees and Y different face sizes. Let di,..., dx be the different degrees of vertices sorted in ascending order: 3 < di < d2 < . .. < dx, 342 Ars Math. Contemp. 8 (2015) 235-244 and let si,..., sY be the different sizes of faces sorted in ascending order: 3 < si < S2 < ... < sy. Again let vdi, resp. fSi, be the number of vertices with degree dj, resp. faces with size sj. We denote the total number of vertices, resp. edges and faces, by V, resp. E and F. This means we have X X £vdi = V J^djVdi = 2E i=1 i=1 YY £ fsi = F £ f =2E I Si =1 i=1 Substituting this in Euler's formula gives X Y X Y 4£ Vdi + 4£ fsi = J2 di Vdi + Y. sifsi + 8 i=1 i=1 i=1 i=1 which simplifies to XY £(4 - di)vdi + £(4 - si)fsi =8. (3.9) Since these are all positive numbers and di and si are at least 3, this formula gives us that at least one of d1 and s1 is equal to 3. It is immediately clear that X and Y are at least 2. Assume that G is a 2, Y-alternating plane graph. This means that there are only two different vertex degrees and they form a 2-colouring of the vertices. So G is bipartite and thus contains no odd cycles. This also implies that all si are even and thus s1 = 3. This gives us that d1 = 3. Substituting this information in (3.9) gives Y Vdx + (4 - d2)vd2 + £(4 - si)fsi = 8. (3.10) i=1 <0 Note that d1 = 3 also implies that Y is at least 3. If X = 2, we also have that d1vdl = d2vd2 = E, since each vertex is only adjacent to vertices with a different degree. So we have that 3vdi = d2vd2. (3.11) Combining (3.10) and (3.11), we find that 2Y (4 - -d2)vd2 +£(4 - si)fsi = 8. 3 i=1 <0 From this it follows that 4 - 2 d2 > 0, I. Althofer et al.: Alternating plane graphs 343 and so d2 =4 or d2 = 5. This means that all 2, Y-alternating plane graphs have degrees 3 and 4 or degrees 3 and 5. We can find lower bounds for the number of vertices in 2, Y-alternating plane graphs. We can rewrite (3.10) as Y vdl + (4 - d2)vd2 = 8 + - 4/. (3.12) i=i Since di = 3, there are at least 3 different face sizes and all face sizes are even, since the graph is bipartite. This means that the left hand side in (3.12) is at least 14 (one face of size 4, one of size 6 and one of size 8). So we find: vdl +(4 - d2)vd2 > 14. (3.13) If d2 = 4, then (3.13) implies that ni > 14 and, combined with (3.11), this also implies n2 > 11, so we get: V = vdl + vd2 > 25. If d2 = 5, then (3.13) implies that vdl - vd2 > 14. Combined with (3.11), this implies that vdl > 35 and vd2 > 21, so we get: V = vdl + vd2 > 56. This shows that the minimum order of 2, Y-alternating plane graphs lies out of reach of the exhaustive search described in Section 4. However, the restrictions imposed on the relation between the number and size of faces and the number and degree of vertices are quite strong, so we conjecture that there exist no 2, Y-alternating plane graphs. The situation changes if we relax the definition of alternating plane graph to also allow for vertices of degree 2. This is explained in Section 9. 4 Exhaustive search In this section we describe the exhaustive search that was used to verify the minimality of the two alternating plane graphs with 17 vertices. The algorithm described here checks each plane graph with a given number of vertices for being an alternating plane graph. The number of plane graphs however increases too fast with increasing number of vertices to be able to verify all graphs up to 17 vertices in an acceptable time span (see Table 1). Therefore we apply several bounding criteria which prune the graphs so that not all plane graphs need to be verified individually. We use the algorithm described in [2] to generate plane graphs with a given number of vertices. In this algorithm plane graphs are generated by starting from triangulations and removing edges of triangles to obtain the other plane graphs. That each plane graph can be constructed by this algorithm can be realised by looking at the reverse process. We can recursively add an edge between two vertices at distance 2 in a face of size greater than 3. This can be done until we end up with a triangulation. In order to avoid isomorphic graphs the algorithm in [2] uses McKay's canonical construction path method. A plane graph G is the parent of a plane graph G', if in the algorithm described above G' is obtained from G by removing an edge. A plane graph G is an ancestor of a plane graph G' if there exist plane graphs Gi,..., Gn such that G is the parent of Gi, Gj is the parent of Gi+i for 1 < i < n and Gn is the parent of G'. 344 Ars Math. Contemp. 8 (2015) 235-244 n Graphs 4 1 5 2 6 9 7 48 8 429 9 4 794 10 64 968 11 954 362 12 14 791 881 13 237 306 720 14 3 910 739 201 15 65 870 458 907 16 1 130 289 662 773 17 19 709 446 129 094 Table 1: The number of 1-connected plane simple graphs with n vertices. This table was constructed using plantri. The next lemmas follow immediately from the fact that a vertex degree can only decrease during the process above and that the minimum degree is 3. Lemma 4.1. A plane graph with two adjacent vertices of degree 3 is never an ancestor of an alternating plane graph. Lemma 4.2. A plane graph with a triangle with vertices of degree 3, 4 and 4 is never an ancestor of an alternating plane graph. These two lemmas have been used to implement a modification of the program plantri in order to only generate alternating plane graphs. As can be seen in Table 2, Lemma 4.1 gives the most restrictions on the generation process. This motivates our choice to implement the modifications to generate alternating plane graphs as follows. After an edge is removed we check whether we can prune the graph based on Lemma 4.1. During an edge removal only two vertices change their degree. If either of these vertices have degree 3, we need to check whether there are any neighbours with degree 3. Then the algorithm from [2] continues and checks whether the edge removal was canonical. If this test also passes, we then check to see whether the graph can be pruned based on Lemma 4.2. When the algorithm finds a graph that it wants to output, we still need to check it for being an alternating plane graph. However, the number of graphs that remain to be checked, is considerably smaller than when just using such a filter on the unmodified algorithm from [2]. The results of the exhaustive search are shown in Table 3. As can be seen, the running time increases greatly near the end of the table. To obtain these results the jobs were split into several parts. These were run on 2.26 GHz Intel Xeon Nehalem processors and 2.6 GHz Intel Xeon Sandy Bridge processors. The time needed per job is not evenly distributed: some jobs were finished in less than a minute, while other jobs still needed more I. Althofer et al.: Alternating plane graphs 345 Lemma 4.1 Lemma 4.2 Lemma 4.1 and Lemma 4.2 n Graphs Ratio Graphs Ratio Graphs Ratio 4 1 100.0% 1 100.0% 1 100.0% 5 1 50.0% 1 50.0% 1 50.0% 6 3 33.3% 6 66.7% 3 33.3% 7 14 29.2% 30 62.5% 13 27.1% 8 105 24.5% 273 63.6% 85 19.8% 9 1 039 21.7% 2 901 60.5% 786 16.4% 10 13 073 20.1% 37 549 57.8% 9 164 14.1% 11 179 961 18.9% 533 883 55.9% 119 395 12.5% 12 2 616 640 17.7% 8 034 607 54.3% 1 664 062 11.2% 13 39 229 044 16.5% 125 435 404 52.9% 24 075 368 10.1% 14 601 955 195 15.4% 2 013 603 025 51.5% 358 017 589 9.2% 15 9 410 493 660 14.3% 33 047 399 191 50.2% 5 438 015 472 8.3% 16 149 488 913 702 13.2% 552 519 039 867 48.9% 84 066 660 749 7.4% 17 2 408 166 869 587 12.2% 9 385 351 956 659 47.6% 1 319 262 418 144 6.7% Table 2: The influence of Lemma 4.1 and Lemma 4.2 on the number of graphs. The ratio shows what percentage of graphs remain to be checked for being an alternating plane graph compared to the total number of plane graphs on n vertices. than a week. This uneven distribution makes it difficult to also obtain the results for 20 vertices even when we split the generation into many jobs. 5 Heuristic searches This section describes the implementation of the algorithm, which was used to find (3,4,5)-alternating plane graphs with 17, 20, 21,..., 41,42 vertices and also some other alternating plane graphs with certain sought properties. The basic idea of the algorithm is to grow a (3,..., x)-alternating plane graph with exactly N vertices by starting with a smallest face (e.g., a triangle) as the current graph and then systematically adding one face at at time "at the border" of the current graph, using backtracking when it becomes obvious that no solution (or no better solution than the best solution found so far) can be found. Note that the border of the faces added so far is also a face of the graph, which we call the exterior face. We call the other faces interior faces. The degree of already created interior faces never changes during the construction and adjacent interior faces always have different degree, i.e., fulfill the face constraint. Vertices adjacent only to interior faces (no longer at the border) are called interior vertices. Their degree also cannot change and so they always have to have different degree (fulfill the vertex constraint). The recursive search takes a graph represented by the faces added so far and the current border and then recursively tries all possible ways to add a new face at the border. Listing 1 gives an overview. The recursive search first checks, if any interior vertices violate the vertex constraint. In that case it backtracks, because the degree of interior vertices does not change by adding faces at the border and so the vertex constraint cannot be fulfilled. Then a lower bound on the number of edges needed to fix vertex constraint violations between border vertices or between border and interior vertices is computed. If the algorithm has already found a 346 ArsMath. Contemp. 8(2015)297-318 recursiveSearch (currentGraph , remaining number of vertices) { return , if interior vertices violate the vertex — constraint or if no solution with less edges than the best solution found so far is possible . probe hashtable check , if a solution has been found generate all feasible branches s o r t them fo r branches add face to graph recursiveSearch remove added face remember current graph in hashtable }_ Listing 1: Recursive search generateBranches(currentGraph) { for s = start — vertex of the new face for e = end—vertex of the new face for n = 0...N— nVertices new vertices to add g e n e r ate b ranch n—p ath b etween s and e g e n e r ate b ranch n—p ath b etween e and s check if the new branches are feasible } Listing 2: Generating branches I. Althofer et al.: Alternating plane graphs 347 solution, it does not search for solutions with more edges. Now, the algorithm probes a hashtable to check if an equivalent graph has been visited previously by the recursive search. The hash table stores the current border (number of vertices, degree of each vertex, degree of each (interior) face on border edges) and the number of vertices and edges used so far. However, it does not store the vertex indices of the border vertices or any interior vertices/faces of the current graph. So on the one hand, the hashing only detects some isomorphisms, but on the other hand, it prevents the algorithm from extending on a current graph, which only differs from a previously searched graph (with identical border vertex degrees and faces) at irrelevant interior vertices/faces. Unlike the exhaustives search in Section 4 the algorithm does not generate all alternating plane graphs but it can be used to find at least one alternating plane graph with sought properties (e.g., a (3,4,5)-alternating plane graph with 17 vertices). If the current graph is a valid alternating plane graph with the sought properties (e.g., a (3,4, 5)-alternating plane graph with 17 vertices), it is returned. Otherwise the search continues by generating all feasible branches. Each feasible branch adds one face at the border of the current graph by adding a single edge or a n-path between two border vertices. The program can be run to search the whole searchspace or (when just trying to find a graph) as a beamsearch. In beamsearch mode, successor nodes of the search are ordered heuristically and only the best X successors are searched. Listing 2 shows how branches are generated. For all pairs of border-vertices s and e and each number n of vertices to be added, generateBranches() tries to generate two branches. The first connects s to e by a n-path and the second connects e to s by a n-path. A branch is feasible if • the degree of the new face is valid (e.g., 3 < degree < 5 for a (3,4, 5)-alternating plane graph ), and • the face-constraint between the new face and interior faces is valid. At the root of the search tree (when adding the second face to the first face), some extra rules are used to prevent generating (too many) isomorphic graphs. For n < 17, the number of nodes needed to fully search (3,4,5)-alternating plane graphs with n vertices is roughly four times that of n — 1. For n =18 and n =19 that factor increases to about 25. This behaviour is caused by the diminishing effect of the hashtable on the number of nodes searched, when the size of the graph increases. 6 List of constructed alternating plane graphs As can be seen in Table 3, the exhaustive search shows that the smallest alternating plane graphs have 17 vertices. Both are (3,4,5)-alternating plane graphs, have 8 triangles, 5 quadrangles and 4 pentagons, and are self-dual. Figure 2 on the left shows the graph found by Frank Schneider using the heuristic search and on the right the graph found in Ghent using the exhaustive search. The minimality of the 17-vertex graphs has been confirmed by an independent implementation. 348 Ars Math. Contemp. 8 (2015) 235-244 n Graphs Time 4 0 0.0 s 5 0 0.0 s 6 0 0.0 s 7 0 0.0 s 8 0 0.0 s 9 0 0.0 s 10 0 0.0 s 11 0 0.2 s 12 0 2.1 s 13 0 31.4 s 14 0 ~ 7.9 min 15 0 « 2.0 hours 16 0 « 1.3 days 17 2 « 16.4 days 18 0 « 301.3 days 19 5 « 13.1 years Table 3: The number of 1-connected alternating plane graphs found by the exhaustive search described in Section 4. For the largest orders, the jobs were split into several parts and the cumulated running time is given. These were run on 2.26 GHz Intel Xeon Nehalem processors and 2.6 GHz Intel Xeon Sandy Bridge processors. Figure 2: The two smallest alternating plane graphs: on the left Schneider-17 and on the right Ghent-17. The vertices of degree 3, resp. 4 and 5, are shown with triangles, resp. squares and pentagons. The faces of size 3, resp. 4 and 5, are shown in dark gray, resp. white and light gray. 350 Ars Math. Contemp. 8 (2015) 235-244 nr V F r dual author vertices faces 3 4 5 6 7 8 3 4 5 6 7 8 9 10 11 12 1 17 17 C2 S FS 8 5 4 8 5 4 2 17 17 C2 S FS, GG 8 5 4 8 5 4 3 19 19 Ci 6 GG 9 6 3 1 9 5 5 4 19 19 C3 S GG 9 6 3 1 9 6 3 1 5 19 19 Ci S GG 9 6 3 1 9 6 3 1 6 19 19 Ci 3 GG 9 5 5 9 6 3 1 7 19 19 C3 S GG 9 6 3 1 9 6 3 1 8 20 20 Ci S FS 9 6 5 9 6 5 9 21 21 C2 S FS 10 5 6 10 5 6 10 22 22 Ci 11 FS 10 6 6 10 6 6 11 22 22 Ci 10 FS 10 6 6 10 6 6 12 22 22 C2 13 FS 10 6 6 10 6 6 13 22 22 C2 12 FS 10 6 6 10 6 6 14 23 23 Ci 15 FS 10 7 6 10 7 6 15 23 23 Ci 14 FS 10 7 6 10 7 6 16 23 23 C2 17 FS 10 7 6 10 7 6 17 23 23 C2 16 FS 10 7 6 10 7 6 18 24 24 Ci 19 FS 10 8 6 10 8 6 19 24 24 Ci 18 FS 10 8 6 10 8 6 20 25 25 Ci 21 KNLS 12 6 6 1 12 8 2 3 21 25 25 Ci 20 KNLS 12 8 2 3 12 6 6 1 22 25 25 C3 23 KS 12 6 6 1 12 9 0 4 23 25 25 C3 22 KS 12 9 0 4 12 6 6 1 24 25 25 C2 S FS 10 9 6 10 9 6 25 25 25 C2 26 KS 12 7 4 2 12 7 4 2 26 25 25 C2 25 KS 12 7 4 2 12 7 4 2 27 26 26 Ci 28 FS 11 8 7 11 8 7 28 26 26 Ci 27 FS 11 8 7 11 8 7 29 27 27 Ci S FS 11 9 7 11 9 7 30 28 28 Ci S FS 11 10 7 11 10 7 31 29 29 Ci 32 FS 12 9 8 12 9 8 32 29 29 Ci 31 FS 12 9 8 12 9 8 33 29 31 Ci 37 KS 12 8 6 3 15 9 7 34 30 30 Ci 36 FS 12 10 8 12 10 8 35 30 33 Ci 46 FS 12 9 5 3 1 16 11 6 36 30 30 Ci 34 FS 12 10 8 12 10 8 37 31 29 Ci 33 KS 15 9 7 12 8 6 3 38 31 31 Ci S FS 12 11 8 12 11 8 39 32 32 Ci S FS 12 12 8 12 12 8 40 32 32 Ci 41 FS 12 12 8 12 12 8 41 32 32 Ci 40 FS 12 12 8 12 12 8 42 32 32 C2 43 KS 14 10 6 2 16 8 6 1 01 43 32 32 C2 42 KS 16 8 6 1 0 1 14 10 6 2 44 33 33 Ci 45 FS 13 11 9 13 11 9 45 33 33 Ci 44 FS 13 11 9 13 11 9 46 33 30 Ci 35 FS 16 11 6 12 9 5 3 1 47 33 33 C2 49 KS 14 10 8 1 16 8 8 0 01 48 33 33 C2 50 KS 16 11 2 2 2 16 8 6 3 49 33 33 C2 47 KS 16 8 8 0 0 1 14 10 8 1 50 33 33 C2 48 KS 16 8 6 3 16 11 2 2 2 51 34 34 Ci 52 FS 13 12 9 13 12 9 Continued on next page I. Althofer et al.: Alternating plane graphs 351 Table 4 - Continued from previous page nr V F r dual author vertices faces 3 4 56 7 8 3 4 5 6 78 9 10 11 12 52 34 34 Ci 51 FS 13 12 9 13 12 9 53 34 32 C 2 N KS 16 10 8 16 8 6 0 01 0 1 54 34 33 Ci N KS 16 10 62 15 8 8 1 1 55 34 34 Ci N KS 16 10 5 2 1 16 9 8 0 01 56 35 35 Ci S FS 13 13 9 13 13 9 57 35 35 C2 N KS 16 11 44 16 10 8 0 01 58 35 36 Ci 59 KS 17 10 42 1 1 17 10 8 0 1 59 36 35 Ci 58 KS 17 10 80 1 17 10 4 2 11 60 36 36 Ci 61 FS 14 12 10 14 12 10 61 36 36 Ci 60 FS 14 12 10 14 12 10 62 36 34 Ci N KS 17 11 71 15 9 7 2 01 63 37 37 Ci S FS 14 13 10 14 13 10 64 37 37 C2 65 KS 16 11 82 16 10 10 1 65 37 37 C2 64 KS 16 10 10 1 16 11 8 2 66 37 38 Ci 70 KS 17 10 63 1 18 10 9 0 1 67 37 38 Ci 77 KS 16 10 8 2 0 1 18 11 10 68 38 38 Ci S FS 14 14 10 14 14 10 69 38 36 C2 N KS 18 12 62 18 9 6 2 00 0 001 70 38 37 Ci 66 KS 18 10 90 1 17 10 6 3 1 71 38 38 Ci 72 KS 18 10 64 18 10 7 2 1 72 38 38 Ci 71 KS 18 10 72 1 18 10 6 4 73 38 39 Ci 78 KS 17 10 9 1 0 1 18 10 10 1 74 39 39 Ci 75 FS 14 15 10 14 15 10 75 39 39 Ci 74 FS 14 15 10 14 15 10 76 39 37 Ci N KS 18 11 10 18 8 8 2 00 0 1 77 39 37 C2 67 KS 18 11 10 16 10 8 2 01 78 39 38 Ci 73 KS 18 10 10 1 17 10 9 1 01 79 39 39 C2 80 KS 18 9 10 2 18 10 10 0 01 80 39 39 C2 79 KS 18 10 10 0 0 1 18 9 10 2 81 40 40 Ci 82 FS 15 14 11 15 14 11 82 40 40 Ci 81 FS 15 14 11 15 14 11 83 40 42 D2 85 KS 16 10 12 2 20 10 12 84 41 41 Ci S FS 15 15 11 15 15 11 85 42 40 D2 83 KS 20 10 12 16 10 12 2 86 42 42 Ci 87 FS 15 16 11 15 16 11 87 42 42 Ci 86 FS 15 16 11 15 16 11 88 44 42 C2 N KS 20 12 12 18 10 12 1 01 Table 4: An overview of all the alternating plane graphs constructed for this paper. The first column gives a number for each alternating plane graph. The second column gives the number of vertices. The third column gives the number of faces. The fourth column gives the symmetry group r. If the graph does not have a simple dual, then the fifth column contains the letter N. If the graph is selfdual, then the fifth column contains the letter S, otherwise the fifth column contains the number of the dual of this graph. The sixth column gives the author of the graph: FS = Frank Schneider, GG = Ghent group, KNLS = Katrin Nimczick and Lisa Schreiber, KS = Karl Scherer. The remaining columns give the number of vertices for each degree and the number of faces for each number of sides. 352 Ars Math. Contemp. 8 (2015) 235-244 Figure 3: Glueing alternating plane graphs together by identifying vertices in the exterior face. 7 Glueing alternating plane graphs together The idea for this technique is quite simple: take two alternating plane graphs A and B, place them apart so that they do not intersect, then identify some of the "exterior" vertices and check whether the result is an alternating plane graph. This is best explained with an example. In Figure 3 two copies of a (3,4, 5)-alternating plane graph with 17 vertices and 17 faces each are displayed. If we identify the vertex of degree 3 at the lower left of the top alternating plane graph with the vertex of degree 5 at the upper left of the bottom alternating plane graph, and the vertex of degree 5 at the lower right of the top alternating plane graph with the vertex of degree 3 at the upper right of the bottom alternating plane graph and remove the identified edge, we obtain the alternating plane graph shown on the right side of Figure 3, which has 32 vertices and 32 faces. Note that the new alternating plane graph is not a (3,4,5)-alternating plane graph anymore. Two vertices now have degree 6, one face has size 6 (the exterior face) and one face has size 8. The degrees of all other vertices and faces are unchanged. Let us look at the left of Figure 3 again. If we identify the vertex of degree 3 at the lower left of the top alternating plane graph with the vertex of degree 3 at the upper right of the bottom alternating plane graph, we obtain a new alternating plane graph with 33 vertices and 33 faces, as shown in Figure 4. Note that the new alternating plane graph is not a (3,4,5)-alternating plane graph anymore. One of the vertices now has degree 6 and one face has size 8. The degrees of all other vertices and faces are unchanged. This new alternating plane graph is also only 1-connected. Looking at both examples it is clear how we can concatenate an unlimited number of alternating plane graphs to make larger and large alternating plane graphs. Using the I. Althofer et al.: Alternating plane graphs 353 Figure 4: An alternating plane graph obtained by identifying two vertices of degree 3 in the left part of Figure 3 alternating plane graphs that were found by the heuristic and exhaustive search, we obtain the following result. Theorem 7.1. For any n > 19 there exists a 3-edge-connected alternating plane graph on n vertices. 8 Large (3,4,5)-alternating plane graphs In the previous section we showed that for any n > 19 there exists an alternating plane graph on n vertices. The size of the faces and the degree of the vertices can however increase vastly using the construction described there. In this section we show that for each number n > 111 there exists an (3,4,5)-alternating plane graph on n vertices. At the basis of the construction lie the 4 building blocks A, B, C, D shown in Figure 5. We will first describe how to construct a (3,4,5)-alternating plane graph from these building blocks. All black vertices in the building blocks have degrees 3, 4 or 5. No vertex of degree 3, 4 or 5 is adjacent to a vertex with the same degree. The white vertices are only adjacent to vertices of degree 5. All faces, except the face in the middle and the exterior face, have size 3, 4 or 5. No face of size 3, 4 or 5 is adjacent to a face with the same size. The face in the middle and the exterior face are only adjacent to faces of size 5. The building blocks have 21, 22, 23 and 24 vertices for A, B, C, D respectively. To combine two building blocks the three white vertices in the middle face of one block need to be identified one by one with a white vertex in the exterior face of the other block. An example is shown in Figure 6. The identified vertices all have degree 4 and are still only adjacent to vertices of degree 5. The newly created faces have size 4 and are only adjacent to faces of size 5. The new graph is again a building block with the same properties, but if the two original building blocks had n1 and n2 vertices, then this new building block has 354 Ars Math. Contemp. 8 (2015) 235-244 Figure 5: The four building blocks that are used to construct a (3,4,5)-alternating plane graph on n vertices for any n > 111. I. Althofer et al.: Alternating plane graphs 355 Figure 6: The combination of the A-block (inner level) and the D-block (outer level). The identified vertices are shown in gray. The new faces are also highlighted in gray. 356 ArsMath. Contemp. 8(2015)297-318 n\ + n2 - 3 vertices. If you combine a copies of the building block with 21 vertices, b copies of the one with 22 vertices, c copies of the one with 23 vertices and d copies of the one with 24 vertices, then the number of vertices in the new block will be 21a + 22b + 23c + 24d - 3(a + b + c + d - 1), which can be rewritten as 18a + 19b + 20c + 21d +3. Once you have a building block of the desired size, you still need to turn it into a (3,4,5)-alternating plane graph. This can be done by connecting one white vertex in the hexagon to the other two in the same hexagon. This replaces the hexagon by two triangles and a quadrangle. The two triangles are not adjacent and the hexagon itself was only adjacent to pentagons. The white vertices now have degrees 3, 3 and 4. The two vertices of degree 3 are not adjacent, and the white vertices were only adjacent to vertices of degree 5. So the graph is still an alternating plane graph. After doing this for both hexagons (the central and the outside one), the graph will be a (3,4,5)-alternating plane graph. Theorem 8.1. For any n > 111 there exists a (3,4,5)-alternating plane graph on n vertices Proof. By taking a copies of building block A, b copies of B, c copies of C and d copies of D, you get a (3,4,5)-alternating plane graph with 18a + 19b + 20c + 21d +3 vertices. The Frobenius number[1] of 18, 19, 20 and 21 is equal to 107, so we can write each number larger than 110 in the form 18a + 19b + 20c + 21d + 3. □ For a (3,4,5)-alternating plane graph constructed by the technique above, if we colour each vertex with its degree in the (3,4,5)-alternating plane graph, then the subgraphs iso-morphic to the subgraph that corresponds to the gray faces in Figure 6 can only appear between two blocks. This shows that any isomorphism between two (3,4,5)-alternating plane graphs constructed by the technique above will always map building blocks to building blocks. Together with the freedom we have in rotating and mirroring building blocks A through D and interchanging building block D with building block D' (see Figure 7), we get the following corollary. Corollary 8.2. The number of (3,4,5)-alternating plane graphs on n vertices grows exponentially with n. 9 Weak alternating plane graphs One way we can relax the conditions for alternating plane graphs, is by allowing vertices of degree 2. These graphs are called weak alternating plane graphs. Definition 9.1. A plane graph is called a weak alternating plane graph, when the following conditions are fulfilled: • There are no adjacent vertices with the same degree. • There are no adjacent faces with the same size. • Each vertex has degree at least 2. • Each face has size at least 3. A weak alternating plane graph is called an X, Y-weak alternating plane graph if there are exactly X different vertex degrees and Y different face sizes. I. Althofer et al.: Alternating plane graphs 357 Figure 7: A second building block with 24 vertices. 9.1 Non-existence for vertex degrees 2 and k with k > 11 For weak alternating plane graphs it is clear that 2, Y-weak alternating plane graphs do exist, e.g., take a 3-regular plane graph, substitute each edge by a digon and then subdivide each edge by a vertex. A first result we can prove is that there exists no weak alternating plane graph with degrees 2 and k for k > 11. We do this in two steps. Lemma 9.2. There exists no weak alternating plane graph with vertex degrees 2 and k for k > 12. Proof. Let G be a weak alternating plane graph with degrees 2 and k. Let v, e, f respectively denote the number of vertices, the number of edges and the number of faces. Euler's Formula says: v + f = e + 2. (9.1) Let fj denote the number of faces with j sides. Since the graph is bipartite, all f j for j odd are 0. Due to the definition of weak alternating plane graph, f2 is also equal to 0. Let ers denote the number of edges between r-faces and s-faces. It is rfr = ^2 er,s. (9.2) s>2 We denote this sum by Sr, so (9.2) is equivalent to f _ Sr Jr — . r If we look at all the sums, then we see that er s occurs two times for each pair (r, s): namely in fr and in fs , so we have: f = E fr = E (^ + ef) . (9.3) r>2 4 vk = (9.7) Combining (9.6) and (9.7), we find ^2 k Putting v- and /-values together gives via (9.5) and (9.8) 1 + 1 ) e. (9.8) v+/< G + k)e+ T2e = ( k + T2)e. (9.9) If we combine (9.1) and (9.9), we get e + 2 < + e, which is equivalent to 2+T2e < ke. (9.10) For all k > 12, inequality (9.10) does not hold. □ In order to show that there exist no weak alternating plane graph with vertex degrees 2 and 11, we first need the following lemma. Lemma 9.3. A plane multigraph containing no faces of size 2 has a vertex of degree at most 5. Proof. Let G be a plane multigraph containing no faces of size 2. Each face contains at least three edges, and each edge is contained in two faces. If we combine this with Euler's Formula, we get e < 3v — 6. (9.11) Let S be the minimum degree of G. Each vertex is incident to at least S edges. Each edge contains 2 vertices. This gives Sv < 2e. Combining this with (9.11), we find 12 < (6 — S)v. Since v is positive, this means that S is at most 5. □ I. Althofer et al.: Alternating plane graphs 359 Lemma 9.4. There exists no weak alternating plane graph with vertex degrees 2 and 11. Proof. Let G be a weak alternating plane graph with vertex degrees 2 and 11. Let G' be the graph obtained from G by smoothing out the vertices of degree 2, i.e., removing each vertex v of degree 2 and connecting the vertices that were neighbours of v. This graph G' can be a multigraph, but since G was a weak alternating plane graph, there are no neighbouring faces of size 2 in G'. All vertices in G' have degree 11. Let G'' be the graph obtained from G' by replacing each face of size 2 by a single edge. This means that G'' is a plane multigraph containing no faces of size 2 and all vertices have degree at least 6. This is a contradiction with Lemma 9.3. □ Theorem 9.5. There exists no weak alternating plane graph with vertex degrees 2 and k for k > 11. Proof. This follows immediately from Lemma 9.2 and Lemma 9.4. □ 9.2 Existence for vertex degrees 2 and k with k < 10 If a 2, Y-weak alternating plane graph exists with degrees 2 and k, then we can show the following result. Lemma 9.6. Let G(V, E) be a 2, Y-weak alternating plane graph with degrees 2 and k. The number of vertices |V | is a multiple of f+2. So if k is even, then |V | is a multiple of fY2 and if k is odd, then |V | is a multiple of k + 2. Proof. Denote by V2 the set of vertices with degree 2 and by Vf the set of vertices with degree k. Since each edge is incident to exactly one vertex of each degree, we have that |E| = 2|V2| = k|Vk|. So we find that |V| = |V2| + |Vf| = f |Vf | + |Vf| = ^|Vf |. □ There is a bijection between the weak alternating plane graphs with degrees 2 and k and the vertex-alternating k-angulations with minimum degree 2. Take any weak alternating plane graph with degrees 2 and k. First we smooth out the vertices of degree 2, i.e., we remove the vertex and the two incident edges and connect the two remaining endpoints by a new edge which replaces the two removed edges in the cyclic order for each of the two endpoints. This operations gives a k-regular, plane multigraph that is face-alternating. If we take the dual of this, then we get a vertex-alternating k-angulations with minimum degree 2. The other way around, it is clear to see that applying the inverse of this process to a vertex-alternating k-angulations with minimum degree 2 always leads to a weak alternating plane graph with degrees 2 and k. We used this bijection to generate weak alternating plane graphs with degrees 2 and k. For k = 3 and k = 4, we generated k-angulations using the program plantri and filtered out those k-angulations that are vertex-alternating. For 5 < k < 10, we used the data obtained in [4] and filtered out those k-angulations that are vertex-alternating. For k = 9 and k = 10, the available data was not sufficient to find any weak alternating plane graphs with degrees 2 and k. The results are shown in Table 5. Although no weak alternating plane graphs with degrees 2 and 10 were found using the exhaustive method described in the previous paragraphs, it is clear that they exist due to the following construction for weak alternating plane graphs with degrees 2 and k from 2 -regular plane graphs for k even. Take a f -regular plane graph. Replace each of its edges by a digon. This results in a k-regular, face-alternating, plane multigraph. Finally subdivide 360 Ars Math. Contemp. 8 (2015) 235-244 Figure 8: An infinite family of 5-regular plane graphs that can be used to construct weak alternating plane graphs with degrees 2 and 10. Figure 9: The first two members of an infinite family of 5-regular plane graphs that can be used to construct weak alternating plane graphs with degrees 2 and 9. A face-alternating matching is shown in bold in each graph. each edge with a vertex to obtain a weak alternating plane graph with degrees 2 and k. Since there exist infinite families of 2-regular plane graphs (the cycles), 3-regular plane graphs (e.g., the prisms), 4-regular plane graphs (e.g., the anti-prisms) and 5-regular plane graphs (e.g., the family shown in Figure 8), this implies that there are infinitely many weak alternating plane graphs with degrees 2 and 4 (respectively 2 and 6, 2 and 8, and 2 and 10). A similar construction can also be used to find weak alternating plane graphs with degrees 2 and 9. A face-alternating matching is a matching in a plane graph that has the property that for each edge e in the matching, e is incident with two faces with distinct sizes. Take a -regular plane graph together with a face-alternating matching. Replace each of its edges that is not in the matching by a digon. This results in a k-regular, face-alternating, plane multigraph. Finally subdivide each edge with a vertex to obtain a weak alternating plane graph with degrees 2 and k. Since there exist infinite families of 3-regular plane graphs with face-alternating matchings (e.g., the prisms on 4n vertices with n > 3), 4-regular plane graphs with face-alternating matchings (e.g., the anti-prisms on 4n vertices with n > 2) and 5-regular plane graphs with face-alternating matchings (e.g., the family shown in Figure 9), this implies that there are infinitely many weak alternating plane graphs with degrees 2 and 5, respectively 2 and 7, and 2 and 9. I. Althofer et al.: Alternating plane graphs 361 n\k 5 6 7 8 9 12 15 16 18 20 21 24 25 27 28 30 32 33 35 36 39 40 42 45 48 50 51 55 43 316 2 420 19 648 165 724 1 437 049 1 1 2 7 19 43 125 368 1 264 4 744 18 723 78 657 338 945 1 518 480 139 4 731 11 10 1 83 3 4 1 4 1 0 1 6 7 1 1 0 1 1 Table 5: The number of weak alternating plane graphs with degrees 2 and k on n vertices found using the technique described in Section 9. Due to Lemma 9.6 the orders are always integers and multiples of k^2. 362 Ars Math. Contemp. 8 (2015) 235-244 10 Conjectures and open problems • As was explained in Section 3, one conjecture which our intuition suggests is the following. Conjecture 10.1. There are no 2, Y-alternating plane graphs and no X, 2-alternat-ing plane graphs. • What the typical parameters are for large alternating plane graphs is still an open problem. E.g., if we let r be the number of vertices of degree 3 in a (3,4,5)-alternating plane graph, then we know from Theorem 3.2 that the number of vertices of degree 4 is in the interval [r - 5, §r - 5]. The question is, given this interval, how are the alternating plane graphs distributed. Is there a density function on the interval [1,1.5] which gives the asymptotic fractions of (3,4,5)-alternating plane graphs for large vertex numbers n? If so, what does the density function look like? • The exhaustive search showed that there are no (3,4,5)-alternating plane graphs on less than 17 vertices and on 18 and 19 vertices. The heuristic search found (3,4,5)-alternating plane graphs on all numbers of vertices from 20 to 42. In Section 8 we showed that (3,4,5)-alternating plane graphs exist on all numbers of vertices starting from 111, but the same construction can also construct (3,4,5)-alternating plane graphs on n vertices for n G [21,..., 24] U [39,..., 45] U [57,..., 66] U [75,..., 87] U [93,..., 108]. This means that we do not know whether there exists a (3,4,5)-alternating plane graph on n vertices for n G [46,..., 56] U [67,..., 74] U [88,..., 92] U {109,110}. Conjecture 10.2. For all n > 20 there exist (3,4,5)-alternating plane graphs on n vertices. • In Section 7 we proved that there exist alternating plane graphs on n vertices for any n > 19. The alternating plane graphs that were constructed in that section are not 3-connected, and some are not 2-connected. The (3,4,5)-alternating plane graphs constructed in Section 8 and most of the alternating plane graphs mentioned in Section 6 are 3-connected. That is why we also pose the following conjecture. Conjecture 10.3. For any n > 19 there exists a 3-connected alternating plane graph on n vertices. 11 Concluding remarks One central experience of our investigations is that without computer help we would never have come this far. Only the union of machine power and human creativity together let us achieve the findings in this paper. All the graphs in this paper are also available through the website [8] and can be downloaded from House of Graphs [3] by searching for the keyword apg. Acknowledgements Kathrin Nimczick and Lisa Schreiber found the very first alternating plane graph back in February 2008. In those days, a long thread on alternating plane graphs started in the forum of online game server LittleGolem.net. Thanks to the people who contributed there, in I. Althofer et al.: Alternating plane graphs 363 particular to: wccanard (UK; he proposed the empty graph as an extremely small example of an alternating plane graph; he also immediately mentioned graphs with vertices of degree 2) and to FatPhil (Finland), Carroll (France), Hjallti (Belgium). The whole thread can be found at [9]. We would like to thank Mohammadreza Jooyandeh for providing us with the data obtained in [4]. The computational resources (Stevin Supercomputer Infrastructure) used to create Table 3 were provided by Ghent University, the Hercules Foundation and the Flemish Government - department EWI. References [1] J. L. R. Alfonsin, The Diophantine Frobenius Problem, Oxford University Press, Oxford Lecture Series in Mathematics and Its Applications, 2005. [2] G. Brinkmann and B. D. McKay, Fast generation of planar graphs, MATCH Commun. Math. Comput. Chem. 42(4) (2007), 909-924. http://cs.anu.edu.au/$\sim$bdm/index. html. [3] G. Brinkmann, J. Goedgebeur, H. Melot and K. Coolsaet, House of Graphs: a database of interesting graphs, Discrete Applied Mathematics 161 (2013), 311-314. http://hog.grinvin. org [4] M. Jooyandeh and B. D. McKay, Recursive Generation of k-Angulations, (preprint). [5] K. Scherer, A Puzzling Journey to the Reptiles and Related Animals, Published by the author, 1987. [6] K. Scherer, NUTTS And other Crackers, Published by the author, 1994. http:// karlscherer.com/Mybooks/bknintro.html [7] K. Scherer, New Mosaics, Published by the author, 1997. [8] http://www.althofer.de/alternating-plane-graphs.html [9] http://www.littlegolem.net/jsp/forum/topic2.jsp?forum=1\&topic= 1814