A Kuratowski-type theorem for 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%2F13%3A10135346" target="_blank" >RIV/00216208:11320/13:10135346 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1016/j.comgeo.2012.07.005" target="_blank" >http://dx.doi.org/10.1016/j.comgeo.2012.07.005</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.comgeo.2012.07.005" target="_blank" >10.1016/j.comgeo.2012.07.005</a>

Jazyk výsledku

angličtina

Název v původním jazyce

A Kuratowski-type theorem for planarity of partially embedded graphs

Popis výsledku v původním jazyce

A partially embedded graph (or PEG) is a triple (G, H, H), where G is a graph, H is a subgraph of G, and H is a planar embedding of H. We say that a PEG (G, H, H) is planar if the graph G has a planar embedding that extends the embedding H. We introducea containment relation of PEGS analogous to graph minor containment, and characterize the minimal non-planar PEGS with respect to this relation. We show that all the minimal non-planar PEGS except for finitely many belong to a single easily recognizableand explicitly described infinite family. We also describe a more complicated containment relation which only has a finite number of minimal non-planar PEGS. Furthermore, by extending an existing planarity test for PEGS, we obtain a polynomial-time algorithm which, for a given PEG, either produces a planar embedding or identifies an obstruction.

Název v anglickém jazyce

A Kuratowski-type theorem for planarity of partially embedded graphs

Popis výsledku anglicky

A partially embedded graph (or PEG) is a triple (G, H, H), where G is a graph, H is a subgraph of G, and H is a planar embedding of H. We say that a PEG (G, H, H) is planar if the graph G has a planar embedding that extends the embedding H. We introducea containment relation of PEGS analogous to graph minor containment, and characterize the minimal non-planar PEGS with respect to this relation. We show that all the minimal non-planar PEGS except for finitely many belong to a single easily recognizableand explicitly described infinite family. We also describe a more complicated containment relation which only has a finite number of minimal non-planar PEGS. Furthermore, by extending an existing planarity test for PEGS, we obtain a polynomial-time algorithm which, for a given PEG, either produces a planar embedding or identifies an obstruction.

Druh

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

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

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2013

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

Computational Geometry: Theory and Applications

ISSN

0925-7721

e-ISSN

—

Svazek periodika

46

Číslo periodika v rámci svazku

4

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

27

Strana od-do

466-492

Kód UT WoS článku

000314437000006

EID výsledku v databázi Scopus

—