Testing Planarity of Partially Embedded Graphs
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F15%3A10312944" target="_blank" >RIV/00216208:11320/15:10312944 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1145/2629341" target="_blank" >http://dx.doi.org/10.1145/2629341</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1145/2629341" target="_blank" >10.1145/2629341</a>
Alternative languages
Result language
angličtina
Original language name
Testing Planarity of Partially Embedded Graphs
Original language description
We study the following problem: given a planar graph G and a planar drawing (embedding) of a subgraph of G, can such a drawing be extended to a planar drawing of the entire graph G? This problem fits the paradigm of extending a partial solution for a problem to a complete one, which has been studied before in many different settings. Unlike many cases, in which the presence of a partial solution in the input makes an otherwise easy problem hard, we show that the planarity question remains polynomial-time solvable. Our algorithm is based on several combinatorial lemmas, which show that the planarity of partially embedded graphs exhibits the 'TONCAS' behavior "the obvious necessary conditions for planarity are also sufficient." These conditions are expressed in terms of the interplay between (1) the rotation system and containment relationships between cycles and (2) the decomposition of a graph into its connected, biconnected, and triconnected components. This implies that no dynamic pr
Czech name
—
Czech description
—
Classification
Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GEGIG%2F11%2FE023" target="_blank" >GEGIG/11/E023: Graph Drawings and Representations</a><br>
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2015
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
ACM Transactions on Algorithms
ISSN
1549-6325
e-ISSN
—
Volume of the periodical
11
Issue of the periodical within the volume
4
Country of publishing house
US - UNITED STATES
Number of pages
42
Pages from-to
1-42
UT code for WoS article
000357122300008
EID of the result in the Scopus database
—