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 is another cubic graph together with a 3-edge-coloring of . Each edge of is expanded into exactly four vertices in , one for each choice of a side and endpoint of the edge. An edge in connects each such vertex to the vertex representing the opposite side and same endpoint of ; these edges are by convention colored red. Another edge in connects each vertex to the vertex representing the opposite endpoint and same side of ; these edges are by convention colored blue. An edge in of the third color, yellow, connects each vertex to the vertex representing another edge that meets at the same side and endpoint. An alternative description of is that it has a vertex for each flag of (a mutually incident triple of a vertex, edge, and face). If is a flag,then there is exactly one vertex , edge , and face such that , , and are also flags. The three colors of edges in 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 may be associated with up to four different vertices of the gem. Whenever a cubic graph 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 .To recover and its embedding, interpret each 2-colored cycle of as the face of an embedding 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 . 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. (Wikipedia).
