Clustered planarity testing revisited

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F15%3A10312286" target="_blank" >RIV/00216208:11320/15:10312286 - isvavai.cz</a>

Výsledek na webu

<a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p24" target="_blank" >http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p24</a>

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Clustered planarity testing revisited

Popis výsledku v původním jazyce

We generalize the Hanani-Tutte theorem 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 variantof 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 to at most five vertices can be tested in polynomialtime. 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

We generalize the Hanani-Tutte theorem 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 variantof 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 to at most five vertices can be tested in polynomialtime. We give a new and short proof of this result, using the matroid intersection algorithm.

Druh

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

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

S - Specificky vyzkum na vysokych skolach<br>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

Electronic Journal of Combinatorics

ISSN

1077-8926

e-ISSN

—

Svazek periodika

22

Číslo periodika v rámci svazku

4

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

29

Strana od-do

—

Kód UT WoS článku

—

EID výsledku v databázi Scopus

2-s2.0-84947074447