Testing Planarity of Partially Embedded Graphs

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Testing Planarity of Partially Embedded Graphs

Popis výsledku v původním jazyce

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

Název v anglickém jazyce

Testing Planarity of Partially Embedded Graphs

Popis výsledku anglicky

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

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GEGIG%2F11%2FE023" target="_blank" >GEGIG/11/E023: Kreslení grafů a jejich geometrické reprezentace</a><br>

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2015

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

ACM Transactions on Algorithms

ISSN

1549-6325

e-ISSN

—

Svazek periodika

11

Číslo periodika v rámci svazku

4

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

42

Strana od-do

1-42

Kód UT WoS článku

000357122300008

EID výsledku v databázi Scopus

—