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.

It was given its first definite formal expression under the name "Constellations" by A. Jacques[3][4] but the concept was already extensively used under the name "rotation" by Gerhard Ringel[5] and J.W.T.

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.

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 ).