Combinatorial map

A combinatorial map is a combinatorial object modelling topological structures with subdivided objects. Historically, the concept was introduced informally by J. Edmonds for polyhedral surfaces ^[1] which are planar graphs. It was given its first definite formal expression under the name "Constellations" by A. Jacques ^[2] but the concept was already extensively used under the name "rotation" by Gerhard_Ringel^[3] 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. The concept was later extended to represent higher-dimensional orientable subdivided objects. 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. Note that combinatorial maps were extended to generalized maps that allow also to represent non-orientable objects like the Möbius strip and the Klein bottle. A combinatorial map is a boundary representation model; it represents object by its boundaries.

Motivation

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 can be used, but when we want to represent any type of cells, we need to use cellular topological model, like combinatorial maps or generalized maps.

Planar graph representation

The first works about combinatorial maps ^{[4] [5]} develop combinatorial representations of graphs on surfaces which includes planar graphs: A 2-dimensional combinatorial map (or 2-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.

Intuitively, a 2-map corresponds to a planar graph where each edge is subdivided into two darts (sometimes also called half-edges). 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 (alpha for arête in French), and σ allows one to retrieve vertices (sigma for sommet in French). We define φ = σ o α which gives, for each dart, the next dart of the same face (phi for face also in French).

So, there are two ways to represent a combinatorial map depending if the permutation is σ or φ (see example below). These two representations are dual to each other: vertices and faces are exchanged.

Combinatorial maps example: a plane graph and the two combinatorial maps depending if we use the notation (D, σ, α) or (D, φ, α).

A plane graph

Corresponding combinatorial map (D, σ, α). Darts are represented by numbered segments, σ by gray arrows (example σ(1)=7), two darts linked by α are drawn consecutively and separated by a small bar (example α(1)=2).

Corresponding combinatorial map (D, φ, α). Darts are represented by numbered arrows, two darts linked by ϕ are drawn consecutively (example φ(1)=3) and two darts linked by α are drawn parallel and in reverse orientation (example α(1)=2.

General definition

The definition of combinatorial map in any dimension is given in ^[6] and ^[7]:

An n-dimensional combinatorial map (or n-map) is a (n + 1)-tuple M = (D, β₁, ..., β_n) such that:

• D is a finite set of darts;
• β₁ is a permutation on D;
• β₂, ..., β_n are involutions on D;
• β_i o β_j is an involution if i + 2 ≤ j (i, j ∈ { 1, ,..., n }).

An n-dimensional combinatorial map represents the subdivision of a closed orientable n-dimensional space. A dart is an abstract element which is only required to define one-to-one mappings. The last line of this definition fixes constraints which guarantee the topological validity of the represented object: a combinatorial map represents a quasi-manifold subdivision. The initial definition of 2-dimensional combinatorial maps can be retrieved by fixing n = 2 and renaming σ by β₁ and α by β₂.

See also

• Boundary representation
• Generalized maps
• Quad-edge data structure
• Rotation system
• Simplicial complex
• Winged edge

References

1. ^ Edmonds J., A Combinatorial Representation for Polyhedral Surfaces, Notices Amer. Math. Soc., vol. 7, 1960
2. ^ Jacques A., Constellations et Graphes Topologiques, Colloque Math. Soc. Janos Bolyai, p. 657-672, 1970
3. ^ Ringel G., Map Color Theorem, Springer-Verlag, Berlin 1974
4. ^ Jacques, A. Constellations et propriétés algébriques des graphes topologiques, Ph.D. thesis, Paris 1969
5. ^ Cori R., Un code pour les graphes planaires et ses applications, Astérisque, vol. 27, 1975
6. ^ Lienhardt P., Topological models for Boundary Representation : a comparison with n-dimensional generalized maps, Computer-Aided Design, Vol. 23, no.1, pp. 59-82, 1991
7. ^ Lienhardt P., N-dimensional generalized combinatorial maps and cellular quasi-manifolds, International Journal on Computational Geometry and Applications, Vol. 4, no. 3, pp. 275-324, 1994

External links

• Combinatorial maps in CGAL, the Computational Geometry Algorithms Library:
  • Damiand, Guillaume. "Combinatorial maps". http://www.cgal.org/Pkg/CombinatorialMaps. Retrieved October 2011.