On Edge Intersection Graphs of Paths with 2 Bends
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F16%3A10331585" target="_blank" >RIV/00216208:11320/16:10331585 - isvavai.cz</a>
Výsledek na webu
<a href="http://dx.doi.org/10.1007/978-3-662-53536-3_18" target="_blank" >http://dx.doi.org/10.1007/978-3-662-53536-3_18</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-662-53536-3_18" target="_blank" >10.1007/978-3-662-53536-3_18</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
On Edge Intersection Graphs of Paths with 2 Bends
Popis výsledku v původním jazyce
An EPG-representation of a graph G is a collection of paths in a grid, each corresponding to a single vertex of G, so that two vertices are adjacent if and only if their corresponding paths share infinitely many points. In this paper we focus on graphs admitting EPG-representations by paths with at most 2 bends. We show hardness of the recognition problem for this class of graphs, along with some subclasses. We also initiate the study of graphs representable by unaligned polylines, and by polylines, whose every segment is parallel to one of prescribed slopes. We show hardness of recognition and explore the trade-off between the number of bends and the number of slopes.
Název v anglickém jazyce
On Edge Intersection Graphs of Paths with 2 Bends
Popis výsledku anglicky
An EPG-representation of a graph G is a collection of paths in a grid, each corresponding to a single vertex of G, so that two vertices are adjacent if and only if their corresponding paths share infinitely many points. In this paper we focus on graphs admitting EPG-representations by paths with at most 2 bends. We show hardness of the recognition problem for this class of graphs, along with some subclasses. We also initiate the study of graphs representable by unaligned polylines, and by polylines, whose every segment is parallel to one of prescribed slopes. We show hardness of recognition and explore the trade-off between the number of bends and the number of slopes.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
IN - Informatika
OECD FORD obor
—
Návaznosti výsledku
Projekt
<a href="/cs/project/GA14-10799S" target="_blank" >GA14-10799S: Hyperkrychlové, grafové a hypergrafové struktury</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2016
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ů
Údaje specifické pro druh výsledku
Název statě ve sborníku
GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, WG 2016
ISBN
978-3-662-53536-3
ISSN
0302-9743
e-ISSN
—
Počet stran výsledku
13
Strana od-do
207-219
Název nakladatele
SPRINGER INT PUBLISHING AG
Místo vydání
CHAM
Místo konání akce
Bogazici Univ, Istanbul
Datum konání akce
22. 6. 2016
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
000390176900018