2026-07-20T14:52:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8223 2024-03-06T10:41:49Z ddc:004 open_access

Embedding Graphs into Embedded Graphs Fulek, Radoslav Graph embedding C-planarity Weakly simple polygons 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Radoslav Fulek 2017 Is Part Of LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2017.34 urn:nbn:de:0030-drops-82234 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.34 eng https://creativecommons.org/licenses/by/3.0/legalcode