TY - JOUR
AU - Colin de Verdière, Éric
AU - Magnard, Thomas
AU - Mohar, Bojan
PY - 2022/12/13
Y2 - 2024/02/25
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 -