Regular polyhedron surface tours
by Jan Kristian Haugland

Suppose a particle is moving around on the surface of a polyhedron. As long as it is in the interior of one of the faces, it moves in a
straight line. Any time it reaches an edge, it crosses it and keeps moving on the face on the other side at the same slope relative to that edge.
If it eventually reaches the initial position and direction without having been at a corner, we consider the tour as a planar graph with the
crossing points as vertices, and edges between consecutive crossing points. We call such a graph a regular surface tour for that polyhedron.

If the faces of the polyhedron are either all equilateral triangles or all squares, then there is a simple way to ensure that the tour is finite. On each face,
draw the same section of a triangular or square grid respectively, such that each corner coincides with a grid vertex. Let the particle move parallel to
the grid lines; just not on the lines themselves. We can characterize the grid by how many equal parts the sides are divided into by parallel grid lines.
The sides of triangles are divided into a, b and a+b parts, and the sides of squares are divided into a and b parts, for non-negative coprime integers a and b.

For details on the smallest graphs that come out of this for a specific polyhedron, click here:   Tetrahedron   Cube   Octahedron   Dodecahedron   Icosahedron

There are two infinite families of graphs that apparently occur as regular tours for the cube, the octahedron and the icosahedron simultaneously:

Type A has 2n(n+1) vertices and appears to be a regular tour for the cube with (a, b) = (4n+2, 1) and (3n+2, 3n+1),
for the octahedron with (a, b) = (3n+1, 1), and for the icosahedron with (a, b) = (3n+2, 3n+1) and (5n+2, 1).

Examples of graphs of type A:

Type B has 3n(n+1)/2 vertices and appears to be a regular tour for the cube with (a, b) = (2n+1, 1) and (2n+1, 2[n/2]+1),
for the octahedron with (a, b) = (n+1, n), and for the icosahedron with (a, b) = (2n+1, 2[n/2]+1) and (2n+[n/2]+1 ,1).

Examples of graphs of type B:

Regular polyhedron surface tours with no double edges form a subset of the 4-regular 3-connected planar graphs
having an Eulerian tour for which no two consecutive edges are incident with the same face. Here are the unsigned
Gauss code representations of all such graphs with up to 21 vertices. Based on data from House of Graphs.

8 vertices:1 entry
9 vertices:1 entry
10 vertices:1 entry
11 vertices:1 entry
12 vertices:3 entries
13 vertices:5 entries
14 vertices:17 entries
15 vertices:40 entries
16 vertices:145 entries
17 vertices:355 entries
18 vertices:1264 entries
19 vertices:3931 entries
20 vertices:12999 entries
21 vertices:44727 entries