combinatorial map

The concept of a combinatorial map was introduced informally by J. Edmonds for polyhedral surfaces{{cite journal |first=J. |last=Edmonds |title=A Combinatorial Representation for Polyhedral Surfaces |journal=Notices Amer. Math. Soc. |volume=7 |date=1960 |hdl=1903/24820 }} which are planar graphs. It was given its first definite formal expression under the name "Constellations" by A. Jacques{{cite thesis |first=A. |last=Jacques |title=Constellations et propriétés algébriques des graphes topologiques |date=1969 |type=PhD |publisher=University of Paris |url=https://hal.archives-ouvertes.fr/tel-01591126/}}{{cite journal |first=A. |last=Jacques |title=Constellations et Graphes Topologiques |journal=Colloque Math. Soc. János Bolyai |volume= |issue= |pages=657–672 |date=1970 }} but the concept was already extensively used under the name "rotation" by Gerhard Ringel{{cite book |first=G. |last=Ringel |title=Map Color Theorem |publisher=Springer |date=2012 |isbn=978-3-642-65759-7 |orig-year=1974 |url=}} 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.{{cite journal |first=R. |last=Cori |title=Un code pour les graphes planaires et ses applications |journal=Astérisque |volume=27 |issue= |pages= |date=1975 |doi= |url=http://www.numdam.org/item/AST_1975__27__1_0/ |mr=404045 |zbl=0313.05115 }}

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 {{math|1=M = (D, σ, α)}} such that:

• {{math|1=D}} is a finite set of darts;
• {{math|1=σ}} is a permutation on {{math|1=D}};
• {{math|1=α}} is an involution on {{math|1=D}} with no fixed point.

Intuitively, a combinatorial map corresponds to a graph where each edge is subdivided into two darts (sometimes also called half-edges). The permutation {{math|1=σ}} gives, for each dart, the next dart by turning around the vertex in the positive orientation; the other permutation {{math|1=α}} gives, for each dart, the other dart of the same edge.

{{math|1=α}} allows one to retrieve edges (alpha for arête in French), and {{math|1=σ}} allows one to retrieve vertices (sigma for sommet in French). We define {{math|1=φ = σ ∘ α}} 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 {{math|1=σ}} or {{math|1=φ}} (see example below). These two representations are dual to each other: vertices and faces are exchanged.

An n-dimensional combinatorial map (or n-map) is a (n + 1)-tuple {{math|1=M = (D, β₁, ..., β_n)}} such that:{{cite journal |first=P. |last=Lienhardt |title=Topological models for Boundary Representation : a comparison with n-dimensional generalized maps |journal=Computer-Aided Design |volume=23 |issue=1 |pages=59–82 |date=1991 |doi=10.1016/0010-4485(91)90082-8 |url=}}{{cite journal |first=P. |last=Lienhardt |title=N-dimensional generalized combinatorial maps and cellular quasi-manifolds |journal=International Journal of Computational Geometry and Applications |volume=4 |issue=3 |pages=275–324 |date=1994 |doi=10.1142/S0218195994000173 |url=}}

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

An n-dimensional combinatorial map represents the subdivision of a closed orientable n-dimensional space. The constraint on {{math|1=β_i ∘ β_j}} guarantees the topological validity of the map as a quasi-manifold subdivision. Two-dimensional combinatorial maps can be retrieved by fixing {{math|1=n = 2}} and renaming {{math|1=σ}} by {{math|1=β₁}} and {{math|1=α}} by {{math|1=β₂}}.

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

In combinatorial mathematics, rotation systems (also called combinatorial embeddings or combinatorial maps) 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 (up to orientation-preserving topological equivalence). 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{{harvtxt|Heffter|1891}}, {{harvtxt|Heffter|1898}} and extensively used by Ringel during the 1950s.{{harvtxt|Ringel|1965}} Independently, Edmonds gave the primal form of the theorem{{harvtxt|Edmonds|1960a}}, {{harvtxt|Edmonds|1960b}} and the details of his study have been popularized by Youngs.{{harvtxt|Youngs|1963}} The generalization to multigraphs was presented by Gross and Alpert.{{harvtxt|Gross|Alpert|1974}}

Rotation systems are related to, but not the same as, the rotation maps used by Reingold et al. (2002) 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 (non-circular) 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.

According to the Euler formula we can deduce the genus g of the closed orientable surface defined by the rotation system $(\backslash sigma,\backslash theta)$ (that is, the surface on which the underlying multigraph is 2-cell embedded).{{harvtxt|Lando|Zvonkin|2004}}, formula 1.3, p. 38. Notice that $V=|Z(\backslash sigma)|$, $E=|Z(\backslash theta)|$ and $F=|Z(\backslash sigma\backslash theta)|$. We find that

:$g=1-\backslash frac\{1\}\{2\}(V-E+F)=1-\backslash frac\{1\}\{2\}(|Z(\backslash sigma)|-|Z(\backslash theta)|+|Z(\backslash sigma\backslash theta)|)$

where $Z(\backslash phi)$ denotes the set of the orbits of permutation $\backslash phi$.

• Bollobás–Riordan polynomial
• Boundary representation
• Generalized maps
• Doubly connected edge list
• Quad-edge data structure
• Rotation system
• Simplicial complex
• Winged edge

{{Reflist|refs=

{{cite journal | last1=Bollobás | first1=Béla | last2=Riordan | first2=Oliver | title=A Polynomial Invariant of Graphs On Orientable Surfaces | journal=Proceedings of the London Mathematical Society | publisher=Wiley | volume=83 | issue=3 | year=2001 | issn=0024-6115 | doi=10.1112/plms/83.3.513 | pages=513–531| s2cid=15895860 }}

}}

• {{cite journal

|first1=R. |last1=Cori |first2=A. |last2=Machì

| title = Maps, hypermaps and their automorphisms: a survey

| journal = Expositiones Mathematicae

| volume = 10

| year = 1992

| pages = 403–467

|mr=1190182

}}

• {{cite journal

| first = J. |last=Edmonds

| authorlink = Jack Edmonds

| title = A combinatorial representation for polyhedral surfaces

| journal = Notices of the American Mathematical Society

| volume = 7

| year = 1960a

| pages = 646

}}

• {{cite thesis

| last = Edmonds

| first = John Robert

| type = Masters

| title = A combinatorial representation for oriented polyhedral surfaces

| publisher = University of Maryland

| year = 1960b |hdl=1903/24820

| url = https://drum.lib.umd.edu/bitstream/handle/1903/24820/Edmonds%2c%20J.R..pdf

}}

• {{cite journal

|first1=J. L. |last1=Gross |first2=S. R. |last2=Alpert | title = The topological theory of current graphs

| journal = Journal of Combinatorial Theory, Series B

| volume = 17

| issue = 3

| year = 1974

| pages = 218–233

|mr=0363971

| doi = 10.1016/0095-8956(74)90028-8

| doi-access = free

}}

• {{cite journal

| first = L. |last=Heffter

| title = Über das Problem der Nachbargebiete

| journal = Mathematische Annalen

| volume = 38

| issue = 4

| year = 1891

| pages = 477–508

| doi = 10.1007/BF01203357

| s2cid = 121206491

| url = https://zenodo.org/record/2148015

}}

• {{cite journal

| first = L. |last=Heffter

| title = Über metacyklische Gruppen und Nachbarcontigurationen

| journal = Mathematische Annalen

| volume = 50

| year = 1898

| issue = 2–3

| pages = 261–268

| doi = 10.1007/BF01448067

| s2cid = 120691296

| url = https://zenodo.org/record/2232715

}}

• {{Cite book | last1=Lando | first1=Sergei K. | last2=Zvonkin | first2=Alexander K. | title=Graphs on Surfaces and Their Applications | publisher=Springer-Verlag | series=Encyclopaedia of Mathematical Sciences: Lower-Dimensional Topology II | isbn=978-3-540-00203-1 | year=2004 | volume=141 }}.
• {{cite book

| author1-link = Bojan Mohar |first1=Bojan |last1=Mohar

| author2-link =Carsten Thomassen (mathematician) |first2=Carsten |last2=Thomassen

| title = Graphs on Surfaces

| publisher = Johns Hopkins University Press

| year = 2001

| isbn = 0-8018-6689-8}}

• {{cite journal

|first1=O. |last1=Reingold |first2=S. |last2=Vadhan |first3=A. |last3=Wigderson

| title = Entropy waves, the zig-zag graph product, and new constant-degree expanders

| journal = Annals of Mathematics

| volume = 155

| issue = 1

| year = 2002

| pages = 157–187

|mr=1888797

| doi = 10.2307/3062153

| jstor = 3062153

|arxiv=math/0406038|s2cid=120739405 }}

• {{cite journal

| first = G. |last=Ringel

| authorlink = Gerhard Ringel

| title = Das Geschlecht des vollständigen paaren Graphen

| journal = Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg

| volume = 28

| issue = 3–4

| year = 1965

| pages = 139–150

|mr=0189012

| doi = 10.1007/BF02993245

| s2cid = 120414651

}}

• {{cite journal

| first = J. W. T. |last=Youngs

| title = Minimal imbeddings and the genus of a graph

| journal = Journal of Mathematics and Mechanics

| volume = 12

| issue = 2

| year = 1963

| pages = 303–315

|mr=0145512

| doi = 10.1512/iumj.1963.12.12021

| doi-access = free

}}

• Combinatorial maps in CGAL, the Computational Geometry Algorithms Library:
• {{cite web

| last = Damiand | first = Guillaume

| title = Combinatorial maps

| url = https://doc.cgal.org/latest/Combinatorial_map

| access-date=February 6, 2021

}}

• Combinatorial maps in [https://cgogn.github.io CGoGN], Combinatorial and Geometric modeling with Generic N-dimensional Maps
• {{nlab|id=combinatorial+map|title=Combinatorial map}}

Category:Algebraic topology

Category:Topological graph theory

Category:Computer graphics data structures

Category:Graph data structures

Category:Planar graphs