What the heck are graph-encoded maps?

A wireframe model of an octahedron uses only 12 wires but fails to specify what surface is being described (in other words, the wireframe specifies the abstract graph, but not its embedding.)  A graph-encoded map of the octahedron needs 24 wires in each of three colors (72 in total), but succeeds in specifying the surface up to topological equivalence.

What has three colors, a wire of each color at each junction, and encodes a surface?

Graph-encoded maps (gems) are just the thing for anyone who would rather think about surfaces and maps visually rather than algebraically. This is a short introduction to graph-encoded maps for those who might be inclined to put them to use. It will be seen that understanding gems makes it easy to understand relations between maps that may seem at first perplexing, e.g., dual, Petrie dual, phial, antimap, etc. Deep insights like map permutations become almost obvious.

A graph is a collection of edges having vertices at both ends. We allow the same two vertices to be at the ends of multiple distinct edges (parallel edges) and we allow the same vertex to be at both ends of an edge (a self-loop.) A graph is not necessarily connected (it may have multiple components), but we will be dealing here exclusively with connected (single component) graphs.

A practical use for graphs, especially in computer graphics and generative art, is to describe and subdivide a surface. A proper embedding of a graph in a closed surface is a drawing of the graph on the surface without any crossing lines, and such that, if all the lines of the drawing were to dematerialize, the surface would fall apart into simply-connected pieces. (It follows immediately that only a connected graph can be properly embedded.) By requiring the surface to fall apart into simply-connected pieces we are requiring that the drawing have enough lines in the right places to fully reveal all the topologically significant details of the surface such as the presence of a handle or a cross-cap.

A map is a proper embedding of a graph in a surface considered up to topological equivalence.

A Tait-colored graph is a graph in which each edge has been assigned one of 3 colors, and every vertex has exactly three incident edges, one of each color. (It follows immediately that a Tait-colored graph cannot have a loop.) It turns out that we never have to deal with any other kinds of graphs if we don't want to, nor with any of their various embeddings in surfaces. Wilson (1979) and Lins (1982) found that anything we might say on these meaty subjects can be just as well expressed as Tait-colorings of abstract trivalent graphs. How simple!

Given a map, any drawing of the map on its surface is locally planar (topologically speaking) provided we stay within the scope of the simply-connected faces surrounding one vertex.  Staying within that limited scope, we can construct what is known as the barycentric subdivision of the map as follows.

We color the vertex at the center of our local scope with the 0-color because a vertex is a 0-dimensional component of the map. Here we identify the 0-color with BLACK.

We construct a mid-edge vertex on each edge incident to the (now black) vertex at the center of our scope (unless such a mid-edge vertex has already been constructed) and color these mid-edge vertices with the 1-color because an edge is a 1-dimensional component of the map. We identify the 1-color with WHITE.

We construct a mid-face vertex in the middle of each face surrounding the black vertex at the center of our local scope (unless such a mid-face vertex has already been constructed) and color these mid-face vertices with the 2-color because a face is a 2-dimensional component of the map. We identify the 2-color with PINK.

Now we construct new edges connecting the (black) vertex at the center of our local scope to its surrounding (pink) mid-face vertices, and also construct new edges connecting the mid-face vertices to the (white) mid-edge vertices within the scope (if such edges have not already been constructed.)

By repeating this construction for each vertex, what emerges is a new map, an Eulerian triangular (triangle-faced) map of the same surface (it is Eulerian because an even number of edges—and triangles—meet at each vertex.) In particular, the number of triangles meeting at each white, mid-edge vertex is 4; the number of triangles meeting at each pink, mid-face vertex is twice the number of original sides on that face; and the number of triangles meeting at each black, original vertex is twice the number of original edges meeting at that vertex. Every edge in this new triangular map connects vertices of two different colors, so each edge can be systematically colored using the third color, the color not present at either of its endpoints.

The dual of this Eulerian triangular map is a simple map (meaning three edges meet at each vertex) having an even number of sides in each of its faces. We can automatically generate a Tait-coloring for the edges of this map by allowing edges to inherit the color of the dual edge.

Using the "good 'n plenty" coloring scheme (0 = black, 1 = white, 2 = pink), every black-white cycle in a gem is a face, every pink-white cycle in a gem is a vertex, and every black-pink cycle in a gem is a 4-cycle representing an edge. Here, the gem—an abstract graph—is shown co-embedded with the original map (a barely visible triangulation) that it completely describes.

Now comes the good news: we can discard at this point the original map, graph, and surface. All can be reconstructed (up to topological equivalence) from the Tait-colored abstract graph—a "bird's nest" in three colors of wire—which is known as a graph-encoded map or gem.

A graph-encoded map of the tetrahedral graph embedded in a sphere (realized in Flexeez.)

Still the same gem. 

Recovering the map

To make a physical model of the surface encoded by a gem (a tricolored "bird's nest"):

1. Give each vertex in the "bird's nest" a number.

2. Cut out an equilateral triangle of mylar drawing film, one for each numbered vertex (if you find that your surface is non-orientable, you will need "ghost mylar" that passes through itself without difficulty.) Mark the vertex number in the center of the triangle, and draw black, white, and pink perpendiculars to the sides. Either of the two possible cyclical orders will do: black-white-pink or black-pink-white. (Since mylar is translucent, we can always flip a triangle over to switch the cyclical order when needed.)

3. Trace the wiring in the "bird's nest" to find the numbers of the black, white, and pink neighbors of each numbered vertex, and so label the correspondingly-colored perpendiculars on its triangle.

4. At this point, no further reference to the gem or "bird's nest" is needed. Assemble the triangles edge-to-edge in accordance with their labels.