Bend-Bounded Path Intersection Graphs: Sausages, Noodles, and Waffles on a Grill

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F12%3A10127532" target="_blank" >RIV/00216208:11320/12:10127532 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/978-3-642-34611-8_28" target="_blank" >http://dx.doi.org/10.1007/978-3-642-34611-8_28</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-642-34611-8_28" target="_blank" >10.1007/978-3-642-34611-8_28</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Bend-Bounded Path Intersection Graphs: Sausages, Noodles, and Waffles on a Grill

Popis výsledku v původním jazyce

In this paper, we study properties of intersection graphs of k- bend paths in the rectangular grid. A k-bend path is a path with at most k 90 degree turns. The class of graphs representable by intersections of k-bend paths is denoted by B(k)-VPG. We showhere that for every fixed k, B(k) -VPG is a strict subset of B(k+1) -VPG and that recognition of graphs from B(k) -VPG is NP-complete even when the input graph is given by a B(k+1)-VPG representation. We also show that the class B(k) -VPG (for k at least 1) is in no inclusion relation with the class of intersection graphs of straight line segments in the plane.

Název v anglickém jazyce

Bend-Bounded Path Intersection Graphs: Sausages, Noodles, and Waffles on a Grill

Popis výsledku anglicky

In this paper, we study properties of intersection graphs of k- bend paths in the rectangular grid. A k-bend path is a path with at most k 90 degree turns. The class of graphs representable by intersections of k-bend paths is denoted by B(k)-VPG. We showhere that for every fixed k, B(k) -VPG is a strict subset of B(k+1) -VPG and that recognition of graphs from B(k) -VPG is NP-complete even when the input graph is given by a B(k+1)-VPG representation. We also show that the class B(k) -VPG (for k at least 1) is in no inclusion relation with the class of intersection graphs of straight line segments in the plane.

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í

2012

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

Lecture Notes in Computer Science

ISSN

0302-9743

e-ISSN

—

Svazek periodika

7551

Číslo periodika v rámci svazku

Summer

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

12

Strana od-do

274-285

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—