Combinatorial map

Combinatorial maps are used as efficient data structures in image representation and processing, in geometrical modeling.

The concept of a combinatorial map was introduced informally by J. Edmonds for polyhedral surfaces[2] which are planar graphs.

[6] 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.

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.

So, there are two ways to represent a combinatorial map depending if the permutation is σ or φ (see example below).

The constraint on βi ∘ βj guarantees the topological validity of the map as a quasi-manifold subdivision.

Two-dimensional combinatorial maps can be retrieved by fixing n = 2 and renaming σ by β1 and α by β2.

Spaces that are not necessarily closed or orientable may be represented using (n-dimensional) generalized maps.

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 (up to orientation-preserving topological equivalence).

This fundamental equivalence between rotation systems and 2-cell-embeddings was first settled in a dual form by Lothar Heffter in the 1890s[9] and extensively used by Ringel during the 1950s.

[10] Independently, Edmonds gave the primal form of the theorem[11] and the details of his study have been popularized by Youngs.

According to the Euler formula we can deduce the genus g of the closed orientable surface defined by the rotation system