Combinatorial maps

Combinatorial maps (nLab ), also known as rotation systems , are combinatorial representations of graphs embedded in surfaces. They are important in topological graph theory and computational geometry. Combinatorial maps can be defined as presheaves subject to mild extra conditions.

In topological graph theory

  • Lando & Zvonkin, 2004: Graphs on surfaces and their applications (doi)
  • Gross, Yellen, Zhang, edgs., 2013: Handbook of graph theory, 2nd ed. (doi), Ch. 7: Topological graph theory
    • Summaries of combinatorial structures are in Sec 7.1.4: “Combinatorial descriptions of maps” and Sec 7.6.5: “Combinatorial schemes”

In combinatorics

  • Gonthier, 2008: Formal proof–the four-color theorem (pdf)
    • Longer technical report: Gonthier, 2005: A computer-checked proof of the four-color theorem (pdf)
    • Explains how hypermaps are used as a computational representation in a formal proof of the four-color theorem
    • States a version of the Jordan curve theorem for hypermaps (Theorem 2)

In computational geometry

Combinatorial maps and related structures are used extensively to represent surfaces in computational geometry:

  • Brisson, 1993: Representing geometric structures in \(d\) dimensions: Topology and order (doi, pdf)
  • Lienhardt, 1994: N-dimensional generalized combinatorial maps and cellular quasi-manifolds (doi)
  • Lienhardt, 1991: Topological models for boundary representation: a comparison with n-dimensional generalized maps (doi)