Graph-encoded map

In topological graph theory, a graph-encoded map or gem is a method of encoding a cellular embedding of a graph using a different graph with four vertices per edge of the original graph. It is the topological analogue of runcination, a geometric operation on polyhedra. Graph-encoded maps were formulated and named by .
Alternative and equivalent systems for representing cellular embeddings include signed rotation systems and ribbon graphs.
The graph-encoded map for an embedded graph formula_1 is another cubic graph formula_2 together with a 3-edge-coloring of formula_2. Each edge formula_4 of formula_1 is expanded into exactly four vertices in formula_2, one for each choice of a side and endpoint of the edge. An edge in formula_2 connects each such vertex to the vertex representing the opposite side and same endpoint of formula_4; these edges are by convention colored red. Another edge in formula_2 connects each vertex to the vertex representing the opposite endpoint and same side of formula_4; these edges are by convention colored blue. An edge in formula_2 of the third color, yellow, connects each vertex to the vertex representing another edge formula_12 that meets formula_4 at the same side and endpoint.
An alternative description of formula_2 is that it has a vertex for each flag of formula_1 (a mutually incident triple of a vertex, edge, and face). If formula_16 is a flag,
then there is exactly one vertex formula_17, edge formula_12, and face formula_19 such that formula_20, formula_21, and formula_22 are also flags. The three colors of edges in formula_2 represent each of these three types of flags that differ by one of their three elements. However, interpreting a graph-encoded map in this way requires more care. When the same face appears on both sides of an edge, as can happen for instance for a planar embedding of a tree, the two sides give rise to different gem vertices. And when the same vertex appears at both endpoints of a self-loop, the two ends of the edge again give rise to different gem vertices. In this way, each triple formula_16 may be associated with up to four different vertices of the gem.
Whenever a cubic graph formula_2 can be 3-edge-colored so that the red-blue cycles of the coloring all have length four, the colored graph can be interpreted as a graph-encoded map, and represents an embedding of another graph formula_1.
To recover formula_1 and its embedding, interpret each 2-colored cycle of formula_2 as the face of an embedding of formula_2 onto a surface,
contract each red--yellow cycle into a single vertex of formula_1, and replace each pair of parallel blue edges left by the contraction with a single edge of formula_1.
The dual graph of a graph-encoded map may be obtained from the map by recoloring it so that the red edges of the gem become blue and the blue edges become red.