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 Lins (1982). Alternative and equivalent systems for representing cellular embeddings include signed rotation systems and ribbon graphs. The graph-encoded map for an embedded graph G {\displaystyle G} is another cubic graph H {\displaystyle H} together with a 3-edge-coloring of H {\displaystyle H} . Each edge e {\displaystyle e} of G {\displaystyle G} is expanded into exactly four vertices in H {\displaystyle H} , one for each choice of a side and endpoint of the edge. An edge in H {\displaystyle H} connects each such vertex to the vertex representing the opposite side and same endpoint of e {\displaystyle e} ; these edges are by convention colored red. Another edge in H {\displaystyle H} connects each vertex to the vertex representing the opposite endpoint and same side of e {\displaystyle e} ; these edges are by convention colored blue. An edge in H {\displaystyle H} of the third color, yellow, connects each vertex to the vertex representing another edge e ′ {\displaystyle e'} that meets e {\displaystyle e} at the same side and endpoint. An alternative description of H {\displaystyle H} is that it has a vertex for each flag of G {\displaystyle G} (a mutually incident triple of a vertex, edge, and face). If ( v , e , f ) {\displaystyle (v,e,f)} is a flag, then there is exactly one vertex v ′ {\displaystyle v'} , edge e ′ {\displaystyle e'} , and face f ′ {\displaystyle f'} such that ( v ′ , e , f ) {\displaystyle (v',e,f)} , ( v , e ′ , f ) {\displaystyle (v,e',f)} , and ( v , e , f ′ ) {\displaystyle (v,e,f')} are also flags. The three colors of edges in H {\displaystyle H} 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 ( v , e , f ) {\displaystyle (v,e,f)} may be associated with up to four different vertices of the gem. Whenever a cubic graph H {\displaystyle H} 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 G {\displaystyle G} . To recover G {\displaystyle G} and its embedding, interpret each 2-colored cycle of H {\displaystyle H} as the face of an embedding of H {\displaystyle H} onto a surface, contract each red--yellow cycle into a single vertex of G {\displaystyle G} , and replace each pair of parallel blue edges left by the contraction with a single edge of G {\displaystyle G} . 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.

Graph describing a topological embedding

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 G {\displaystyle G} is another cubic graph H {\displaystyle H} together with a 3-edge-coloring of H {\displaystyle H} . Each edge e {\displaystyle e} of G {\displaystyle G} is expanded into exactly four vertices in H {\displaystyle H} , one for each choice of a side and endpoint of the edge. An edge in H {\displaystyle H} connects each such vertex to the vertex representing the opposite side and same endpoint of e {\displaystyle e} ; these edges are by convention colored red. Another edge in H {\displaystyle H} connects each vertex to the vertex representing the opposite endpoint and same side of e {\displaystyle e} ; these edges are by convention colored blue. An edge in H {\displaystyle H} of the third color, yellow, connects each vertex to the vertex representing another edge e ′ {\displaystyle e'} that meets e {\displaystyle e} at the same side and endpoint.^[1]

An alternative description of H {\displaystyle H} is that it has a vertex for each flag of G {\displaystyle G} (a mutually incident triple of a vertex, edge, and face). If ( v , e , f ) {\displaystyle (v,e,f)} is a flag, then there is exactly one vertex v ′ {\displaystyle v'} , edge e ′ {\displaystyle e'} , and face f ′ {\displaystyle f'} such that ( v ′ , e , f ) {\displaystyle (v',e,f)} , ( v , e ′ , f ) {\displaystyle (v,e',f)} , and ( v , e , f ′ ) {\displaystyle (v,e,f')} are also flags. The three colors of edges in H {\displaystyle H} 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 ( v , e , f ) {\displaystyle (v,e,f)} may be associated with up to four different vertices of the gem.^[1]

Whenever a cubic graph H {\displaystyle H} 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 G {\displaystyle G} . To recover G {\displaystyle G} and its embedding, interpret each 2-colored cycle of H {\displaystyle H} as the face of an embedding of H {\displaystyle H} onto a surface, contract each red--yellow cycle into a single vertex of G {\displaystyle G} , and replace each pair of parallel blue edges left by the contraction with a single edge of G {\displaystyle G} .^[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.^[3]

References

[edit]

1. ^ ^{a b c d} Bonnington, C. Paul; Little, Charles H. C. (1995), The foundations of topological graph theory, New York: Springer-Verlag, p. 31, doi:10.1007/978-1-4612-2540-9, ISBN 0-387-94557-1, MR 1367285
2. ^ Lins, Sóstenes (1982), "Graph-encoded maps", Journal of Combinatorial Theory, Series B, 32 (2): 171–181, doi:10.1016/0095-8956(82)90033-8, MR 0657686
3. ^ Bonnington & Little (1995), pp. 111–112.