On edge intersection graphs of paths with 2 bends

Kód výsledku v 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>

Výsledek na webu

<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>

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 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.

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 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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

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)

Rok uplatnění

2017

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

Discrete Applied Mathematics

ISSN

0166-218X

e-ISSN

—

Svazek periodika

226

Číslo periodika v rámci svazku

Neuveden

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

11

Strana od-do

106-116

Kód UT WoS článku

000404197000013

EID výsledku v databázi Scopus

2-s2.0-85019551150