Embedding graphs into embedded graphs

R. Fulek, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.

Download
OA 2017_LIPIcs-Fulek.pdf 588.98 KB

Conference Paper | Published | English

Scopus indexed
Department
Abstract
A (possibly degenerate) drawing of a graph G in the plane is approximable by an embedding if it can be turned into an embedding by an arbitrarily small perturbation. We show that testing, whether a drawing of a planar graph G in the plane is approximable by an embedding, can be carried out in polynomial time, if a desired embedding of G belongs to a fixed isotopy class, i.e., the rotation system (or equivalently the faces) of the embedding of G and the choice of outer face are fixed. In other words, we show that c-planarity with embedded pipes is tractable for graphs with fixed embeddings. To the best of our knowledge an analogous result was previously known essentially only when G is a cycle.
Publishing Year
Date Published
2017-12-01
Volume
92
Article Number
34
Conference
ISAAC: International Symposium on Algorithms and Computation
Conference Location
Phuket, Thailand
Conference Date
2017-12-09 – 2017-12-22
IST-REx-ID

Cite this

Fulek R. Embedding graphs into embedded graphs. In: Vol 92. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPICS.ISAAC.2017.34
Fulek, R. (2017). Embedding graphs into embedded graphs (Vol. 92). Presented at the ISAAC: International Symposium on Algorithms and Computation, Phuket, Thailand: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ISAAC.2017.34
Fulek, Radoslav. “Embedding Graphs into Embedded Graphs,” Vol. 92. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPICS.ISAAC.2017.34.
R. Fulek, “Embedding graphs into embedded graphs,” presented at the ISAAC: International Symposium on Algorithms and Computation, Phuket, Thailand, 2017, vol. 92.
Fulek R. 2017. Embedding graphs into embedded graphs. ISAAC: International Symposium on Algorithms and Computation vol. 92.
Fulek, Radoslav. Embedding Graphs into Embedded Graphs. Vol. 92, 34, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPICS.ISAAC.2017.34.
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
Main File(s)
File Name
Access Level
OA Open Access
Date Uploaded
2019-06-04
MD5 Checksum
fc7a643e29621c8bbe49d36b39081f31


Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar