Ribbon graph

In topological graph theory, a ribbon graph is a way to represent graph embeddings, equivalent in power to signed rotation systems or graph-encoded maps.[1] It is convenient for visualizations of embeddings, because it can represent unoriented surfaces without self-intersections (unlike embeddings of the whole surface into three-dimensional Euclidean space) and because it omits the parts of the surface that are far away from the graph, allowing holes through which the rest of the embedding can be seen. Ribbon graphs are also called fat graphs.[2]

A ribbon graph with one vertex (the yellow disk), three edges (two of them twisted), and one face. It represents an embedding of a graph with three self-loops onto the projective plane.

Definition

In a ribbon graph representation, each vertex of a graph is represented by a topological disk, and each edge is represented by a topological rectangle with two opposite ends glued to the edges of vertex disks (possibly to the same disk as each other).[3]

Embeddings

A ribbon graph representation may be obtained from an embedding of a graph onto a surface (and a metric on the surface) by choosing a sufficiently small number , and representing each vertex and edge by their -neighborhoods in the surface.[1][4] For small values of , the edge rectangles become long and thin like ribbons, giving the name to the representation.

In the other direction, from a ribbon graph one may find the faces of its corresponding embedding as the components of the boundary of the topological surface formed by the ribbon graph. One may recover the surface itself by gluing a topological disk to the ribbon graph along each boundary component. The partition of the surface into vertex disks, edge disks, and face disks given by the ribbon graph and this gluing process is a different but related representation of the embedding called a 'band decomposition.[5] The surface onto which the graph is embedded may be determined by whether it is orientable (true if any cycle in the graph has an odd number of twists) and by its Euler characteristic.

The embeddings that can be represented by ribbon graphs are the ones in which a graph is embedded onto a 2-manifold (without boundary) and in which each face of the embedding is a topological disk.[1]

Equivalence

Two ribbon graph representations are said to be equivalent (and define homeomorphic graph embeddings) if they are related to each other that a homeomorphism of the topological space formed by the union of the vertex disks and edge rectangles that preserves the identification of these features.[3] Ribbon graph representations may be equivalent even if it is not possible to deform one into the other within 3d space: this notion of equivalence considers only the intrinsic topology of the representation, and not how it is embedded.

However, ribbon graphs are also applied in knot theory,[4] and in this application weaker notions of equivalence that take into account the 3d embedding may also be used.

References
  1. Dehmer, Matthias (2010), Structural Analysis of Complex Networks, Springer, p. 267, ISBN 9780817647896
  2. "Ribbon graph", nLab, retrieved 2017-12-13
  3. Ellis-Monaghan, Joanna A.; Moffatt, Iain (2013), "1.1.4 Ribbon Graphs", Graphs on Surfaces: Dualities, Polynomials, and Knots, SpringerBriefs in Mathematics, Springer, pp. 5–7, ISBN 9781461469711
  4. Gelca, Răzvan (2014), Theta Functions and Knots, World Scientific, p. 289, ISBN 9789814520584
  5. Ellis-Monaghan & Moffatt (2013), 1.1.5 Band Decompositions, pp. 7–8.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.