On Edge Intersection Graphs of Paths with 2 Bends
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
On Edge Intersection Graphs of Paths with 2 Bends
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GA14-10799S" target="_blank" >GA14-10799S: Hybercubic, graph and hypergraph structures</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2016
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, WG 2016
ISBN
978-3-662-53536-3
ISSN
0302-9743
e-ISSN
—
Number of pages
13
Pages from-to
207-219
Publisher name
SPRINGER INT PUBLISHING AG
Place of publication
CHAM
Event location
Bogazici Univ, Istanbul
Event date
Jun 22, 2016
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000390176900018