A central part of the paper is a description how alternating plane graphs can be generated for all numbers of vertices from 19 on. The proof is partly based on a list of explicitely constructed alternating plane graphs. This table can be found online at

To get on idea of that list, look at the following two images.

The next three pictures show typical ways to merge apg's to get larger ones.

*******************************************************************

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 plane 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 plane graphs with 18 vertices.
**

A **plane 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 plane 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 plane graphs in the **Wolfram Demonstrations
Project**, click
here.

Back in 2008, I was in search of alternating plane 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).

Feb 06, 2008:

Feb 02, 2008:

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

This 3-dimensional realisation of the Schneider graph was made with the 3d-printer of the

Outside of Jena, the first person to touch the Schneider-17 was

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

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 plane 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 plane 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.

Graph drawing by Karl Scherer with help of his program "Graph Puzzles" for "Zillions of Games".

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

My interest in alternating plane graphs comes from work of