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.

[1] It is the topological analogue of runcination, a geometric operation on polyhedra.

Graph-encoded maps were formulated and named by Lins (1982).

[2] Alternative and equivalent systems for representing cellular embeddings include signed rotation systems and ribbon graphs.

The graph-encoded map for an embedded graph

, one for each choice of a side and endpoint of the edge.

connects each such vertex to the vertex representing the opposite side and same endpoint of

; these edges are by convention colored red.

; these edges are by convention colored blue.

(a mutually incident triple of a vertex, edge, and face).

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.

may be associated with up to four different vertices of the gem.

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

and its embedding, interpret each 2-colored cycle of

onto a surface, contract each red--yellow cycle into a single vertex of

, and replace each pair of parallel blue edges left by the contraction with a single edge of

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