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 , 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. 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. Several applications require a data structure to represent the subdivision of an object. For example, a 2D object can be decomposed into vertices (0-cells), edges (1-cells), and faces (2-cells). 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. A combinatorial map is a triplet M = (D, σ, α) such that: D is a finite set of darts; σ is a permutation on D; α is an involution on D with no fixed point.