On edge intersection graphs of paths with 2 bends

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F17%3A10366552" target="_blank" >RIV/00216208:11320/17:10366552 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1016/j.dam.2017.04.023" target="_blank" >http://dx.doi.org/10.1016/j.dam.2017.04.023</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.dam.2017.04.023" target="_blank" >10.1016/j.dam.2017.04.023</a>

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 the plane square 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 poly lines, 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
—

Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

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)

Publication year
2017
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)