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

Objekt anzeigen

• Standort: Deutsche Nationalbibliothek Frankfurt am Main
• Umfang: Online-Ressource
• Sprache: Englisch

Verweise und Beziehungen

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

Beteiligte, Orts- und Zeitangaben

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

Weitere Informationen

• DOI: 10.57717/cgt.v1i1.11
• URN: urn:nbn:de:101:1-2023030400544320016994
• Rechteinformation: Open Access; Der Zugriff auf das Objekt ist unbeschränkt möglich.