2026-08-18T16:11:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8740 2024-03-06T10:42:32Z ddc:004 open_access

Embedding Graphs into Two-Dimensional Simplicial Complexes Verdière, Éric Colin de Magnard, Thomas Mohar, Bojan computational topology embedding simplicial complex graph surface We consider the problem of deciding whether an input graph G admits a topological embedding into a 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 when C is part of the input, and we give a polynomial-time algorithm if the complex C is fixed. Our strategy is to reduce the problem to 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Éric Colin de Verdière and Thomas Magnard and Bojan Mohar 2018 Is Part Of LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2018.27 urn:nbn:de:0030-drops-87401 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.27 eng https://creativecommons.org/licenses/by/3.0/legalcode