Английская Википедия: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.Шаблон:R It is the topological analogue of runcination, a geometric operation on polyhedra. Graph-encoded maps were formulated and named by Шаблон:Harvtxt.Шаблон:R Alternative and equivalent systems for representing cellular embeddings include signed rotation systems and ribbon graphs.
The graph-encoded map for an embedded graph <math>G</math> is another cubic graph <math>H</math> together with a 3-edge-coloring of <math>H</math>. Each edge <math>e</math> of <math>G</math> is expanded into exactly four vertices in <math>H</math>, one for each choice of a side and endpoint of the edge. An edge in <math>H</math> connects each such vertex to the vertex representing the opposite side and same endpoint of <math>e</math>; these edges are by convention colored red. Another edge in <math>H</math> connects each vertex to the vertex representing the opposite endpoint and same side of <math>e</math>; these edges are by convention colored blue. An edge in <math>H</math> of the third color, yellow, connects each vertex to the vertex representing another edge <math>e'</math> that meets <math>e</math> at the same side and endpoint.Шаблон:R
An alternative description of <math>H</math> is that it has a vertex for each flag of <math>G</math> (a mutually incident triple of a vertex, edge, and face). If <math>(v,e,f)</math> is a flag, then there is exactly one vertex <math>v'</math>, edge <math>e'</math>, and face <math>f'</math> such that <math>(v',e,f)</math>, <math>(v,e',f)</math>, and <math>(v,e,f')</math> are also flags. The three colors of edges in <math>H</math> 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 <math>(v,e,f)</math> may be associated with up to four different vertices of the gem.Шаблон:R
Whenever a cubic graph <math>H</math> 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 <math>G</math>. To recover <math>G</math> and its embedding, interpret each 2-colored cycle of <math>H</math> as the face of an embedding of <math>H</math> onto a surface, contract each red--yellow cycle into a single vertex of <math>G</math>, and replace each pair of parallel blue edges left by the contraction with a single edge of <math>G</math>.Шаблон:R
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.[1]
References
- ↑ Шаблон:Harvtxt, pp. 111–112.
