Combinatorial map

Last updated April 08, 2023

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.^[1] More generally, an $n$ -dimensional combinatorial map is a combinatorial representation of a graph on an $n$ -dimensional orientable manifold.

History

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. Youngs in their famous solution of the Heawood map-coloring problem. The term "constellation" was not retained and instead "combinatorial map" was favored.^[6]

Combinatorial maps were later generalized to represent higher-dimensional orientable subdivided objects.

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

Definition

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.

Intuitively, a combinatorial map corresponds to a 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 $φ = σ \circ α$ 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$ ).

Higher-dimensional generalization

An n-dimensional combinatorial map (or n-map) is a (n + 1)-tuple $M = (D, β 1, ..., β n)$ such that:^[7]^[8]

$D$ is a finite set of darts;
$β 1$ is a permutation on $D$ ;
$β 2, ..., β n$ are involutions on $D$ ;
$β i \circ β j$ is an involution if $i + 2 \leq j (i, j \in {1,,..., n})$ .

An n-dimensional combinatorial map represents the subdivision of a closed orientable n-dimensional space. The constraint on $β i \circ β 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.

Related Research Articles

<span class="mw-page-title-main">Simplex</span> Multi-dimensional generalization of triangle

In geometry, a simplex is a generalization of the notion of a triangle or tetrahedron to arbitrary dimensions. The simplex is so-named because it represents the simplest possible polytope in any given dimension. For example,

In mathematics, homology is a general way of associating a sequence of algebraic objects, such as abelian groups or modules, with other mathematical objects such as topological spaces. Homology groups were originally defined in algebraic topology. Similar constructions are available in a wide variety of other contexts, such as abstract algebra, groups, Lie algebras, Galois theory, and algebraic geometry.

In mathematics, and more specifically in algebraic topology and polyhedral combinatorics, the Euler characteristic is a topological invariant, a number that describes a topological space's shape or structure regardless of the way it is bent. It is commonly denoted by $.$

In the mathematical disciplines of topology and geometry, an orbifold is a generalization of a manifold. Roughly speaking, an orbifold is a topological space which is locally a finite group quotient of a Euclidean space.

Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geometric objects, such as points, lines, planes, circles, spheres, polygons, and so forth. The subject focuses on the combinatorial properties of these objects, such as how they intersect one another, or how they may be arranged to cover a larger object.

In combinatorics, an abstract simplicial complex (ASC), often called an abstract complex or just a complex, is a family of sets that is closed under taking subsets, i.e., every subset of a set in the family is also in the family. It is a purely combinatorial description of the geometric notion of a simplicial complex. For example, in a 2-dimensional simplicial complex, the sets in the family are the triangles, their edges, and their vertices.

<span class="mw-page-title-main">Arrangement of lines</span> Subdivision of the plane by lines

In geometry, an arrangement of lines is the subdivision of the plane formed by a collection of lines. Bounds on the complexity of arrangements have been studied in discrete geometry, and computational geometers have found algorithms for the efficient construction of arrangements.

In mathematics, a simplicial set is an object composed of simplices in a specific way. Simplicial sets are higher-dimensional generalizations of directed graphs, partially ordered sets and categories. Formally, a simplicial set may be defined as a contravariant functor from the simplex category to the category of sets. Simplicial sets were introduced in 1950 by Samuel Eilenberg and Joseph A. Zilber.

In algebraic topology, simplicial homology is the sequence of homology groups of a simplicial complex. It formalizes the idea of the number of holes of a given dimension in the complex. This generalizes the number of connected components.

<span class="mw-page-title-main">Triangulation (topology)</span>

In mathematics, triangulation describes the replacement of topological spaces by piecewise linear spaces, i.e. the choice of a homeomorphism in a suitable simplicial complex. Spaces being homeomorphic to a simplicial complex are called triangulable. Triangulation has various uses in different branches of mathematics, for instance in algebraic topology, in complex analysis or in modeling.

In combinatorial mathematics, rotation systems 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.

In graph theory, Vizing's theorem states that every simple undirected graph may be edge colored using a number of colors that is at most one larger than the maximum degree $Δ$ of the graph. At least $Δ$ colors are always necessary, so the undirected graphs may be partitioned into two classes: "class one" graphs for which $Δ$ colors suffice, and "class two" graphs for which $Δ + 1$ colors are necessary. A more general version of Vizing's theorem states that every undirected multigraph without loops can be colored with at most $Δ+µ$ colors, where $µ$ is the multiplicity of the multigraph. The theorem is named for Vadim G. Vizing who published it in 1964.

In topological graph theory, an embedding of a graph $on a surface is a representation of on in which points of are associated with vertices and simple arcs are associated with edges in such a way that:$

Polyhedral combinatorics is a branch of mathematics, within combinatorics and discrete geometry, that studies the problems of counting and describing the faces of convex polyhedra and higher-dimensional convex polytopes.

Clique complexes, independence complexes, flag complexes, Whitney complexes and conformal hypergraphs are closely related mathematical objects in graph theory and geometric topology that each describe the cliques of an undirected graph.

In mathematics, a generalized map is a topological model which allows one to represent and to handle subdivided objects. This model was defined starting from combinatorial maps in order to represent non-orientable and open subdivisions, which is not possible with combinatorial maps. The main advantage of generalized map is the homogeneity of one-to-one mappings in any dimensions, which simplifies definitions and algorithms comparing to combinatorial maps. For this reason, generalized maps are sometimes used instead of combinatorial maps, even to represent orientable closed partitions.

In mathematics, a regular map is a symmetric tessellation of a closed surface. More precisely, a regular map is a decomposition of a two-dimensional manifold into topological disks such that every flag can be transformed into any other flag by a symmetry of the decomposition. Regular maps are, in a sense, topological generalizations of Platonic solids. The theory of maps and their classification is related to the theory of Riemann surfaces, hyperbolic geometry, and Galois theory. Regular maps are classified according to either: the genus and orientability of the supporting surface, the underlying graph, or the automorphism group.

In Mathematics, the Lindström–Gessel–Viennot lemma provides a way to count the number of tuples of non-intersecting lattice paths, or, more generally, paths on a directed graph. It was proved by Gessel–Viennot in 1985, based on previous work of Lindström published in 1973.

In algebraic topology and graph theory, graph homology describes the homology groups of a graph, where the graph is considered as a topological space. It formalizes the idea of the number of "holes" in the graph. It is a special case of a simplicial homology, as a graph is a special case of a simplicial complex. Since a finite graph is a 1-complex, the only non-trivial homology groups are the 0-th group and the 1-th group.

A graph neural network (GNN) is a class of artificial neural networks for processing data that can be represented as graphs.

References

↑ Bollobás, Béla; Riordan, Oliver (2001). "A Polynomial Invariant of Graphs On Orientable Surfaces". Proceedings of the London Mathematical Society. Wiley. 83 (3): 513–531. doi:10.1112/plms/83.3.513. ISSN 0024-6115. S2CID 15895860.
↑ Edmonds, J. (1960). "A Combinatorial Representation for Polyhedral Surfaces". Notices Amer. Math. Soc. 7. hdl:1903/24820.
↑ Jacques, A. (1969). Constellations et propriétés algébriques des graphes topologiques (PhD). University of Paris.
↑ Jacques, A. (1970). "Constellations et Graphes Topologiques". Colloque Math. Soc. János Bolyai: 657–672.
↑ Ringel, G. (2012) [1974]. Map Color Theorem. Springer. ISBN 978-3-642-65759-7.
↑ Cori, R. (1975). "Un code pour les graphes planaires et ses applications". Astérisque. 27. MR 0404045. Zbl 0313.05115.
↑ Lienhardt, P. (1991). "Topological models for Boundary Representation : a comparison with n-dimensional generalized maps". Computer-Aided Design. 23 (1): 59–82. doi:10.1016/0010-4485(91)90082-8.
↑ Lienhardt, P. (1994). "N-dimensional generalized combinatorial maps and cellular quasi-manifolds". International Journal of Computational Geometry and Applications. 4 (3): 275–324. doi:10.1142/S0218195994000173.

External links

Combinatorial maps in CGAL, the Computational Geometry Algorithms Library:
- Damiand, Guillaume. "Combinatorial maps" . Retrieved February 6, 2021.

Combinatorial maps in CGoGN, Combinatorial and Geometric modeling with Generic N-dimensional Maps
Combinatorial map at the nLab

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[br01-1] Bollobás, Béla; Riordan, Oliver (2001). "A Polynomial Invariant of Graphs On Orientable Surfaces". Proceedings of the London Mathematical Society. Wiley. 83 (3): 513–531. doi:10.1112/plms/83.3.513. ISSN 0024-6115. S2CID 15895860.

[2] Edmonds, J. (1960). "A Combinatorial Representation for Polyhedral Surfaces". Notices Amer. Math. Soc. 7. hdl:1903/24820.

[3] Jacques, A. (1969). Constellations et propriétés algébriques des graphes topologiques (PhD). University of Paris.

[4] Jacques, A. (1970). "Constellations et Graphes Topologiques". Colloque Math. Soc. János Bolyai: 657–672.

[5] Ringel, G. (2012) [1974]. Map Color Theorem. Springer. ISBN 978-3-642-65759-7.

[6] Cori, R. (1975). "Un code pour les graphes planaires et ses applications". Astérisque. 27. MR 0404045. Zbl 0313.05115.

[7] Lienhardt, P. (1991). "Topological models for Boundary Representation : a comparison with n-dimensional generalized maps". Computer-Aided Design. 23 (1): 59–82. doi:10.1016/0010-4485(91)90082-8.

[8] Lienhardt, P. (1994). "N-dimensional generalized combinatorial maps and cellular quasi-manifolds". International Journal of Computational Geometry and Applications. 4 (3): 275–324. doi:10.1142/S0218195994000173.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]