Alternating Planar Graphs

Latest Update: September 13, 2013

I designed a 2-player board game "Schneider von Gent" where either the graph Schneider-17 or the Gent-17 are used as game board. Click!



Frank Schneider found an alternating planar graph with 30 vertices, 33 faces, and 61 edges. This refutes a conjecture of Karl Scherer, who thought that the difference between number of vertices and faces coul differ by atmost 2.

Nicolas van Cleemput (Gent University) proved with computer help that there do not exist alternating planar graphs with 18 vertices.



A planar graph is called alternating, when the following conditions are fulfilled:
* There are no neighbouring vertices with the same degree.
* There are no neighbouring faces with the same number of sides. (Attention: the outer face of the graph is also a face!)
* Each vertex has degree at least 3.
* Each face has at least 3 sides.

My motivation to introduce alternating planar graphs in 2008 came from Karl Scherer's nice alternating tilings. Alternating tilings are tilings with several (at least two) types of tiles where no two tiles of the same type touch each other. See for instance Karl's beautiful 20- and 21-solutions for squaring the square here.
The 21-solution became the base for a variant of my game EinStein würfelt nicht. Karl Scherer also has provided a nice website on alternating planar graphs in the Wolfram Demonstrations Project, click here.

Back in 2008, I was in search of alternating planar graphs where one of the following criteria is met:
* Number of vertices is very small - or
* Number of vertices plus number of faces is smaller than 34 (34 = 17 + 17 was from the record holder Schneider-17, by Frank Schneider).


Record Holders

Feb 07, 2013: Gunnar Brinkmann and Nicolas van Cleemput from Ghent University found a second apg with 17 vertices and 17 faces.
Feb 06, 2008: Frank Schneider (Aachen): 17 vertices + 17 faces
Feb 02, 2008: Katrin Nimczick and Lisa Schreiber (Jena): 25 vertices + 26 faces

With massive computer help, the "Ghent group" proved that 17 is the smallest number of vertices for an alternating planar graph. On Feb 07, 2013, they announced that there exist exactly two non-isomorphic alternating planar graphs with 17 vertices: the Schneider graph and another one which I call Gent-17 in contrast to Schneider-17. Both have 17 vertices and 17 faces.








This 3-dimensional realisation of the Schneider graph was made with the 3d-printer of the "Instrumental Analysis Group" of "Ernst-Abbe-Fachhochschule" Jena. Therefore, my thanks to the group, especially to the leader, Prof. Dr. Karl-Heinz Feller, and to his doctoral assistant Konrad Hoffmeier. The 3d-coordinates had been optimized before by Frank Schneider himself.

Outside of Jena, the first person to touch the Schneider-17 was Reinhold Wittig from Göttingen, wise guru ot the German game designer scene.



Carefully, Reinhold took the valuable piece, turned it around several times, and then mumbled: "Here is an axis of symmetry... no, just not ... but now here, no, also not ... but here, no." Then he took up his head and starred at me. "Reinhold", I started softly, "there are no axis of symmetry in this body. This is fully intended."



The three pictures at the end of this page show the Schneider graph in two different drawings (a very nice one by Jan Kristian Haugland from Bergen/Norway; another one by Karl Scherer from New Zealand, with the help of his program "Graph Puzzles" for Zillions of Games) and the Nimczick-Schreiber graph.

Observe that in the Schneider graph all degrees (for vertices and faces) are from 3, 4, 5. Furthermore, this graph is self-dual. Jan Kristian Haugland (alias "Tasmanian Devil" on LittleGolem) found that in each alternating planar graph with the 3,4,5-restriction the number of vertices and the number of faces are equal! His proof may be found here (somewhere in the middle of the lengthy thread).

For some time it was an open question whether each alternating planar graph with (3,4,5)-restriction on the degrees is self-dual. Frank Schneider gave a clear "No" by showing that several of "his" (3,4,5)-apg's are not self-dual.




Frank Schneider: Alternating planar graph with 17 vertices and 17 faces. Graph drawing by Jan Kristian Haugland.


Frank Schneider: 3-dimensional paper realisation of his graph. We intend to make a 3d-version with solid material.




Frank Schneider: Alternating planar graph with 17 vertices and 17 faces
Graph drawing by Karl Scherer with help of his program "Graph Puzzles" for "Zillions of Games".



K. Nimczick and L. Schreiber: the very first apg (with 25 vertices and 25 inner faces)

New Contributions are welcome to the email address mentioned on the main site.

My interest in alternating planar graphs comes from work of Karl Scherer on alternating tilings of a square by smaller squares.

Back to the main site of Ingo Althofer