Clustered planarity testing revisited

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F14%3A10282839" target="_blank" >RIV/00216208:11320/14:10282839 - isvavai.cz</a>

Výsledek na webu

<a href="http://link.springer.com/content/pdf/10.1007%2F978-3-662-45803-7_36.pdf" target="_blank" >http://link.springer.com/content/pdf/10.1007%2F978-3-662-45803-7_36.pdf</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-662-45803-7_36" target="_blank" >10.1007/978-3-662-45803-7_36</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Clustered planarity testing revisited

Popis výsledku v původním jazyce

The Hanani-Tutte theorem is a classical result proved for the first time in the 1930s that characterizes planar graphs as graphs that admit a drawing in the plane in which every pair of edges not sharing a vertex cross an even number of times. We generalize this result to clustered graphs with two disjoint clusters, and show that a straightforward extension to flat clustered graphs with three or more disjoint clusters is not possible. For general clustered graphs we show a variant of the Hanani-Tutte theorem in the case when each cluster induces a connected subgraph. Di Battista and Frati proved that clustered planarity of embedded clustered graphs whose every face is incident with at most five vertices can be tested in polynomial time. We give a new and short proof of this result, using the matroid intersection algorithm.

Název v anglickém jazyce

Clustered planarity testing revisited

Popis výsledku anglicky

The Hanani-Tutte theorem is a classical result proved for the first time in the 1930s that characterizes planar graphs as graphs that admit a drawing in the plane in which every pair of edges not sharing a vertex cross an even number of times. We generalize this result to clustered graphs with two disjoint clusters, and show that a straightforward extension to flat clustered graphs with three or more disjoint clusters is not possible. For general clustered graphs we show a variant of the Hanani-Tutte theorem in the case when each cluster induces a connected subgraph. Di Battista and Frati proved that clustered planarity of embedded clustered graphs whose every face is incident with at most five vertices can be tested in polynomial time. We give a new and short proof of this result, using the matroid intersection algorithm.

Druh

D - Stať ve sborníku

CEP obor

BA - Obecná matematika

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

S - Specificky vyzkum na vysokych skolach<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2014

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 statě ve sborníku

Graph Drawing

ISBN

978-3-662-45802-0

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

12

Strana od-do

428-439

Název nakladatele

Springer Berlin Heidelberg

Místo vydání

Neuveden

Místo konání akce

Würzburg

Datum konání akce

24. 9. 2014

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—