topological graph theory In mathematics, topological graph theory is a branch of graph theory. It studies the embedding of graphs in surfaces, spatial embeddings of graphs, and graphs as topological spaces. It also studies immersions of graphs. Embedding a graph in ...

, a graph-encoded map or gem is a method of encoding a cellular embedding of a

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

using a different graph with four vertices per edge of the original graph. It is the

topological In mathematics, topology (from the Greek words , and ) is concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, without closing ...

analogue of runcination, a geometric operation on

polyhedra In geometry, a polyhedron (plural polyhedra or polyhedrons; ) is a three-dimensional shape with flat polygonal faces, straight edges and sharp corners or vertices. A convex polyhedron is the convex hull of finitely many points, not all on t ...

. 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

G

is another

cubic graph In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs. A bicubic graph is a cubic bipa ...

H

together with a 3-edge-coloring of

H

. Each edge

e

G

is expanded into exactly four vertices in

H

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

H

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

e

; these edges are by convention colored red. Another edge in

H

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

e

; these edges are by convention colored blue. An edge in

H

of the third color, yellow, connects each vertex to the vertex representing another edge

e'

that meets

e

at the same side and endpoint. An alternative description of

H

is that it has a vertex for each

flag A flag is a piece of fabric (most often rectangular or quadrilateral) with a distinctive design and colours. It is used as a symbol, a signalling device, or for decoration. The term ''flag'' is also used to refer to the graphic design emp ...

G

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

(v,e,f)

is a flag, then there is exactly one vertex

v'

, edge

e'

, and face

f'

such that

(v',e,f)

(v,e',f)

, and

(v,e,f')

are also flags. The three colors of edges in

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 In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...

, the two sides give rise to different gem vertices. And when the same vertex appears at both endpoints of a

self-loop In graph theory, a loop (also called a self-loop or a ''buckle'') is an edge that connects a vertex to itself. A simple graph contains no loops. Depending on the context, a graph or a multigraph may be defined so as to either allow or disallow t ...

, the two ends of the edge again give rise to different gem vertices. In this way, each triple

(v,e,f)

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

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

. To recover

G

and its embedding, interpret each 2-colored cycle of

H

as the face of an embedding of

H

onto a

surface A surface, as the term is most generally used, is the outermost or uppermost layer of a physical object or space. It is the portion or region of the object that can first be perceived by an observer using the senses of sight and touch, and is t ...

contract A contract is a legally enforceable agreement between two or more parties that creates, defines, and governs mutual rights and obligations between them. A contract typically involves the transfer of goods, services, money, or a promise to ...

each red--yellow cycle into a single vertex of

G

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

G

. The

dual graph In the mathematical discipline of graph theory, the dual graph of a plane graph is a graph that has a vertex for each face of . The dual graph has an edge for each pair of faces in that are separated from each other by an edge, and a self-loo ...

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., pp. 111–112.

References

{{reflist, refs= {{citation , last1 = Bonnington , first1 = C. Paul , last2 = Little , first2 = Charles H. C. , doi = 10.1007/978-1-4612-2540-9 , isbn = 0-387-94557-1 , location = New York , mr = 1367285 , page = 31 , publisher = Springer-Verlag , title = The foundations of topological graph theory , url = https://books.google.com/books?id=GtjiBwAAQBAJ&pg=PA31 , year = 1995 {{citation , last = Lins , first = Sóstenes , issue = 2 , journal = Journal of Combinatorial Theory , mr = 657686 , pages = 171–181 , series = Series B , title = Graph-encoded maps , doi = 10.1016/0095-8956(82)90033-8 , volume = 32 , year = 1982, doi-access = free Topological graph theory