Embedding Graphs into Two-Dimensional Simplicial Complexes


  • Éric Colin de Verdière LIGM, CNRS, Univ Gustave Eiffel
  • Thomas Magnard LIGM, CNRS, Univ Gustave Eiffel
  • Bojan Mohar Simon Fraser University, Burnaby, BC V5A 1S6, Canada https://orcid.org/0000-0002-7408-6148




We consider the problem of deciding whether an input graph G admits a topological embedding into an input two-dimensional simplicial complex C. This problem includes, among others, the embeddability problem of a graph on a surface and the topological crossing number of a graph, but is more general.

The problem is NP-complete in general (if C is part of the input), and we give an algorithm that runs in polynomial time for any fixed C.

Our strategy is to reduce the problem into an embedding extension problem on a surface, which has the following form: Given a subgraph H' of a graph G', and an embedding of H' on a surface S, can that embedding be extended to an embedding of G' on S? Such problems can be solved, in turn, using a key component in Mohar's algorithm to decide the embeddability of a graph on a fixed surface (STOC 1996, SIAM J. Discr. Math. 1999).




How to Cite

Colin de Verdière, Éric, Magnard, T., & Mohar, B. (2022). Embedding Graphs into Two-Dimensional Simplicial Complexes. Computing in Geometry and Topology, 1(1), 6:1–6:23. https://doi.org/10.57717/cgt.v1i1.11



Original Research Articles