Combinatorial map


A combinatorial map is a combinatorial representation of a graph on an orientable surface. A combinatorial map may also be called a combinatorial embedding, a rotation system, an orientable ribbon graph, a fat graph, or a cyclic graph. More generally, an -dimensional combinatorial map
is a combinatorial representation of a graph on an -dimensional orientable manifold.
Combinatorial maps are used as efficient data structures in image representation and processing, in geometrical modeling. This model is related to simplicial complexes and to combinatorial topology. A combinatorial map is a boundary representation model; it represents object by its boundaries.

History

The concept of a combinatorial map was introduced informally by J. Edmonds for polyhedral surfaces which are planar graphs. It was given its first definite formal expression under the name "Constellations" by A. Jacques but the concept was already extensively used under the name "rotation" by Gerhard Ringel and J.W.T. Youngs in their famous solution of the Heawood map-coloring problem. The term "constellation" was not retained and instead "combinatorial map" was favored.
Combinatorial maps were later generalized to represent higher-dimensional orientable subdivided objects.

Motivation

Several applications require a data structure to represent the subdivision of an object. For example, a 2D object can be decomposed into vertices, edges, and faces. More generally, an n-dimensional object is composed with cells of dimension 0 to n. Moreover, it is also often necessary to represent neighboring relations between these cells.
Thus, we want to describe all the cells of the subdivision, plus all the incidence and adjacency relations between these cells. When all the represented cells are simplexes, a simplicial complex may be used, but when we want to represent any type of cells, we need to use cellular topological models like combinatorial maps or generalized maps.

Definition

A combinatorial map is a triplet such that:
Intuitively, a combinatorial map corresponds to a graph where each edge is subdivided into two darts. The permutation gives, for each dart, the next dart by turning around the vertex in the positive orientation; the other permutation gives, for each dart, the other dart of the same edge.
allows one to retrieve edges, and allows one to retrieve vertices. We define which gives, for each dart, the next dart of the same face.
So, there are two ways to represent a combinatorial map depending if the permutation is or . These two representations are dual to each other: vertices and faces are exchanged.

Higher-dimensional generalization

An n-dimensional combinatorial map is a -tuple such that:
An n-dimensional combinatorial map represents the subdivision of a closed orientable n-dimensional space. The constraint on guarantees the topological validity of the map as a quasi-manifold subdivision. Two-dimensional combinatorial maps can be retrieved by fixing and renaming by and by.
Spaces that are not necessarily closed or orientable may be represented using generalized maps.

Rotation systems

In combinatorial mathematics, rotation systems encode embeddings of graphs onto orientable surfaces by describing the circular ordering of a graph's edges around each vertex.
A more formal definition of a rotation system involves pairs of permutations; such a pair is sufficient to determine a multigraph, a surface, and a 2-cell embedding of the multigraph onto the surface.
Every rotation scheme defines a unique 2-cell embedding of a connected multigraph on a closed oriented surface. Conversely, any embedding of a connected multigraph G on an oriented closed surface defines a unique rotation system having G as its underlying multigraph. This fundamental equivalence between rotation systems and 2-cell-embeddings was first settled in a dual form by Lothar Heffter in the 1890s and extensively used by Ringel during the 1950s. Independently, Edmonds gave the primal form of the theorem and the details of his study have been popularized by Youngs. The generalization to multigraphs was presented by Gross and Alpert.
Rotation systems are related to, but not the same as, the rotation maps used by Reingold et al. to define the zig-zag product of graphs. A rotation system specifies a circular ordering of the edges around each vertex, while a rotation map specifies a permutation of the edges at each vertex. In addition, rotation systems can be defined for any graph, while as Reingold et al. define them rotation maps are restricted to regular graphs.

Characterizing the surface of the embedding

According to the Euler formula we can deduce the genus g of the closed orientable surface defined by the rotation system . Notice that, and. We find that
where denotes the set of the orbits of permutation.