@article{Colin de Verdière_Magnard_Mohar_2022, title={Embedding Graphs into Two-Dimensional Simplicial Complexes}, volume={1}, url={https://cgt-journal.org/index.php/cgt/article/view/11}, DOI={10.57717/cgt.v1i1.11}, abstractNote={<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>}, number={1}, journal={Computing in Geometry and Topology}, author={Colin de Verdière, Éric and Magnard, Thomas and Mohar, Bojan}, year={2022}, month={Dec.}, pages={6:1–6:23} }