Embedding Graphs into Two-Dimensional Simplicial Complexes

Abstract: 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). https://www.cgt-journal.org/index.php/cgt/article/view/11

Object Details

• Location: Deutsche Nationalbibliothek Frankfurt am Main
• Extent: Online-Ressource
• Language: Englisch

References and Relationships

• Bibliographic citation: Embedding Graphs into Two-Dimensional Simplicial Complexes ; volume:1 ; number:1 ; year:2022 ; Computing in Geometry and Topology ; 1, Heft 1 (2022)

Contributors, Places and Time

• Creator: Colin de Verdière, Éric ; Magnard, Thomas ; Mohar, Bojan

Further information

• DOI: 10.57717/cgt.v1i1.11
• URN: urn:nbn:de:101:1-2023030400544320016994
• Rights: Open Access; Der Zugriff auf das Objekt ist unbeschränkt möglich.
• Last update: 14.08.2025, 10:51 AM CEST