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.

An exchange move that preserves tricolorability

Edge-coloring of the connectivity map for the completely foldable triangle grid.

When the edges of the connectivity map are colored the same as the edges of the triangulation (the triangle edges being colored with the mean of the node colors at each end,) left-right, geodesic paths (Petrie paths) cycle through three colors, and facial cycles cycle through two colors.

By shifting branches past each other two-past-two, and then swapping the colors of two edges, a doubled exchange can be made that preserves tricolorability.

An exchange move that preserves tricolorability.

An expansion move that preserves complete foldability

An expansion move that preserves the tricolorability (complete foldability) of  a triangulation.

Like the Pachner moves in the previous post, the composite move that preserves the tricolorability or tripartite-ness of a triangulation has a dual version that acts  on the trivalent connectivity map.

The expansion move acts on the dual connectivity map (dashed lines) in a predictable way.

Expansion in the connectivity map is simply the insertion of a digon in an edge. This increases face count by one, vertex count by 2, edge count by 3.

Expansion in the connectivity map is simply the insertion of a digon in an edge.

Moves that preserve the tricolorability of the triangulation preserve the local bipartite-ness of the connectivity map.

Exchange and expansion: Dual versions of the Pachner moves

Expansion and exchange moves, dual versions of the Pachner moves. Image quoted from Bilson-Thompson et al., "Update on braids and preons."

Each of the Parchner moves (and their compositions) has an equivalent in the dual map, the 3-regular (a.k.a., trivalent or cubic) map that directs the connectivity of the triangles in the triangulation.

Exchange = dual version of flip₂₂ = Find a 3-edge path that turns left-then-right or right-then-left. Slide the two non-path, branch edges past each other. Leaves the face, vertex, and edge counts unchanged. In fullerene chemistry this is the Stone-Wales transformation.

Expansion = dual version of flip₁₃ : truncate a (trivalent) vertex, creating a trianglular face in its place. Increases face count by 1, vertices by 2, and edges by 3.

Contraction = dual version of flip₃₁ = contract a trianglular face, leaving a trivalent vertex in its place. Decreases face count by 1, vertices by 2, and edges by 3.

Mutating completely foldable triangulations

If we have a completely foldable (CF) triangulation in hand, we might be able to mutate it into another CF triangulation by making local "moves" that preserve its tricolorability.

It is known that a sequence of Pachner moves (a.k.a., bistellar flips) connect any two triangulations of the same surface.

The three Pachner moves are:

flip₂₂ = rotate the edge shared by two triangles (this move is self-inverse.)
flip₁₃ = trisection one triangle into three triangles by adding one vertex and three edges to its interior.
flip₃₁ = weld together the three triangles around a trivalent vertex by removing the vertex and its three incident edges (this is the inverse of flip13.)

None of the Pachner moves preserve the tricolorability of a triangulation by themselves. Rotate creates four non-Eulerian vertices when applied to a triangulation that is already tricolorable. Trisection does the same. Weld cannot even be applied to a tricolorable triangulation since it needs a trivalent vertex. 

The tricolorability-preserving mutation we are looking for, if it exists, must be expressible as a composition of Pachner moves.

There are nine possible 2-move compositions of Pachner moves, and these may have variations depending on which edge or triangle we choose operate on in the second move.

We can immediately eliminate the 2-move compositions that begin with weld since there are no trivalent vertices to be found in a triangulation that is tricolorable. For like reasons, we can eliminate the 2-move compositions that end with trisection since this would leave us with a trivalent vertex in the triangulation making it non-tricolorable.

The three remaining possibilities are:

rr: rotate-then-rotate: an identity when the same edge is operated on in the second move; the first rotation creates four non-Eulerian vertices and there is simply no way to repair them all with a subsequent rotation of any other edge.

rw: rotate-then-weld: this fails in the general case because there is no guarantee that the edge rotation of the first move will produce a trivalent vertex to weld in the second move. The special cases when an edge rotation produces a trivalent vertex are: I, when at least one of the vertices the edge rotates away from has valence 4, and II, when at least one of the vertices the edge rotates toward has valence 2.

tr: trisection-then-rotate: this works any time the rotation acts on one of the three edges created in the first move. Rotating some other edge in the second move would leave a trivalent vertex from the first move, making the triangulation non-tricolorable.

tw: trisection then weld: this is an identity since the only trivalent vertex available to weld is the one created in he first move.

So the only 2-move composition of Pachner moves that preserves tricolorability is tr, more explicitly, "trisection a triangle, then rotate one of the new edges." The action of tr is to increase the count of vertices by 1, faces by 2, and edges by 3.

In visual terms, tr parallellizes an edge and then separates the two parallel edges with a bisected edge.

With hindsight we can construct an inverse for tr from special case II of rw as follows. If any vertex in a triangulation has valence 2, it must lie between two parallel edges (else its incident faces could not both be triangles.) Finding such a 2-valent vertex, we can rotate either of its opposing parallel edges, making said vertex 3-valent, and then remove the vertex with weld. Note that this rw acts as the inverse of tr regardless of which of the two opposing parallels gets rotated and ultimately removed.

That gives us tr, which can grow a tricolorable triangulation, and rw, which can shrink one, leaving us still in the hunt for a mutation that can interconvert tricolorable triangulations of the same size.

What tr means physically is that we slit open one edge of the triangulation (creating the two parallel edges) and repair the wound by gluing on a triangular envelope that has been likewise slit open one on edge. The net result is that we have joined a triangular "ear" to the surface. The 2-valent vertex is the point of the ear. Inversely, rw finds such an ear and removes it.

Clearly, slit-and-join is a general technique we can use to compose any two completely foldable triangulations (CFT's) along a doubled common edge. If we imagine this surgery occurring when both CFT's are completely folded, the final move is simply to fold on the coincident common edges so that we once again have a single triangle.

Generating completely foldable triangulations

Tripartite subdivision of an icosahedron.

When the triangles of the above mesh are made equilateral, the resulting polyhedron (a stellation of the rhombic triacontahedron) is completely foldable. The paper model itself is rigid, but the surface has an alternate conformation as a stack of triangles.

As shown by Di Francesco and Guitter, the necessary and sufficient condition for a closed surface composed of equilateral triangles to be completely foldable is that its graph is tripartite. Given a surface mesh (or, topologically speaking, a map,) they teach a simple way to generate a tripartite triangulation (triangle-faced map) of the same surface.

Construction: Given a map with black vertices, bisect every edge with a white vertex; place a pink vertex in the center of each face and connect it to the white and black vertices incident to that face.

The construction is equivalent to the map operation Meta (a.k.a. barycentric subdivision, full bisection, 2-D subdivision, dual triangle quadrisection,) and as well the construction that locates the preimages of 0, 1, and ∞ in a dessin d'enfants.

Completely foldable surfaces

What kinds of closed, triangulated surfaces can be completely folded up into a single triangle?

The classic interest of origami is folding up a portion of the plane (usually a square sheet of paper) into a more appealing or useful shape, but physicists interested in 2-D quantum gravity have been looking at folding from a different direction: what kinds of closed, triangulated surfaces can be folded up into a small triangular portion of the plane?

Di Francesco and Guitter have shown that any vertex-tricolorable mesh of equilateral triangles can be phantom-folded to a single triangle. By phantom-folding we mean that the surface is allowed to pass through and coincide with itself in its folded state; by vertex-tricolorable (a.k.a., properly 3-colorable, or tripartite) we mean that we can assign one of three colors to each vertex of the mesh such that no two adjacent vertices receive the same color. When completely folded into a single triangle—or even just partially folded onto the plane—we find that the coincident vertices share the same color. Di Francesco and Guitter's result holds for any genus of surface, orientable or not.

Vertex-tricoloring a triangulation is rigid: coloring the three vertices of a single triangle forces all the rest. The coloring goes easily or not at all. The underlying graph must be tripartite for the coloring to succeed. Whenever an equilateral triangulation folds onto a portion of the plane, it has three vertex classes, and their spatial arrangement will conform exactly to a vertex tricoloring of the plane equivalent to this one. A subsidiary tricoloring of edges (not a proper edge coloring) results by simply mixing the vertex colors of each edge's endpoints. This edge coloring does direct a proper edge coloring of the dual, trivalent graph that describes the triangles' connectivity.

A surface mesh composed of equilateral triangles necessarily gives a rather crinkled approximation to a smooth surface (see image below.) Adding a requirement of vertex-tricolorability exacerbates this. A necessary (but not sufficient) condition for vertex-tricolorability is that there be an even number of triangles around each vertex. (Place three—or any odd number—of equilateral triangles around a vertex and try folding the ensemble flat!) That means surface curvature can only be coded by clusters of 6, 4, 8, etc., equilateral triangles around a vertex—we forfeit the option to approximate surface curvature with clusters of 3, 5, 7, etc., triangles. Completely foldable surfaces will in general look quite crumpled even in their fully extended state. C'est la vie.

A surface composed of equilateral triangles is crinkly-looking even before we require the triangulation to be Eulerian (i.e., to have an even number of triangles around each vertex, such a triangulation is locally tripartite.) Image quoted from Isenburg, Gumhold and Gotsman, "Connectivity Shapes."

By the way, to physicists, the curvature we are talking about is the quantized gravitational curvature of a 2-D spacetime, a curvature induced by the presence of matter. Constraints that we may find vitally useful (i.e., foldability) sometimes just make for more interesting behavior in their models.