TY - JOUR AU - Colin de Verdière, Éric AU - Magnard, Thomas AU - Mohar, Bojan PY - 2022/12/13 Y2 - 2024/03/29 TI - Embedding Graphs into Two-Dimensional Simplicial Complexes JF - Computing in Geometry and Topology JA - CompGeomTop VL - 1 IS - 1 SE - Original Research Articles DO - 10.57717/cgt.v1i1.11 UR - https://cgt-journal.org/index.php/cgt/article/view/11 SP - 6:1-6:23 AB - <p>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.</p><p>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.</p><p>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).</p> ER -