Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2018.27
URN: urn:nbn:de:0030-drops-87401
URL: https://drops.dagstuhl.de/opus/volltexte/2018/8740/
Verdière, Éric Colin de ; Magnard, Thomas ; Mohar, Bojan
Embedding Graphs into Two-Dimensional Simplicial Complexes
| pdf-format: |
|
Abstract
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).
BibTeX - Entry
@InProceedings{verdire_et_al:LIPIcs:2018:8740,
author = {{\'E}ric Colin de Verdi{\`e}re and Thomas Magnard and Bojan Mohar},
title = {{Embedding Graphs into Two-Dimensional Simplicial Complexes}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {27:1--27:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Bettina Speckmann and Csaba D. T{\'o}th},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8740},
URN = {urn:nbn:de:0030-drops-87401},
doi = {10.4230/LIPIcs.SoCG.2018.27},
annote = {Keywords: computational topology, embedding, simplicial complex, graph, surface}
}
| Keywords: | computational topology, embedding, simplicial complex, graph, surface | |
| Seminar: | 34th International Symposium on Computational Geometry (SoCG 2018) | |
| Issue date: | 2018 | |
| Date of publication: | 08.06.2018 |
