On Edge Intersection Graphs of Paths with 2 Bends

Martin Pergel , Paweł Rzążewski

Abstract

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.
Author Martin Pergel
Martin Pergel,,
-
, Paweł Rzążewski ZSPI
Paweł Rzążewski,,
- Department of Information Processing Systems
Pages207-219
Publication size in sheets0.6
Book Heggernes P. (eds.): GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, WG 2016, Lecture Notes In Computer Science, vol. 9941, 2016, SPRINGER INT PUBLISHING AG, ISBN 978-3-662-53536-3, [978-3-662-53535-6]
Keywords in Englishgeometric intersection graphs, bend graphs, bend number
Abstract in PolishReprezentacją EPG grafu G nazywamy funkcję ze zbioru wierzchołków G w zbiór ścieżek na prostokątnej planarnej siatce, w której dwie ścieżki dzielą krawędź siatki wtedy i tylko wtedy odpowiadające im wierzchołki połączone są krawędzią. W pracy pokazujemy, że problem rozpoznawania, czy dany graf ma reprezentację EPG, gdzie każda ścieżka ma co najwyżej 2 punkty zgięcia, jest NP-zupełny. Pokazujemy też trudność rozpoznawania pewnych podklas tej klasy grafów.
DOIDOI:10.1007/978-3-662-53536-3_18
URL http://link.springer.com/chapter/10.1007/978-3-662-53536-3_18
Languageen angielski
Score (nominal)15
ScoreMinisterial score [Punktacja MNiSW] = 15.0, 28-06-2017, BookChapterSeriesAndMatConf
Ministerial score (2013-2016) [Punktacja MNiSW (2013-2016)] = 15.0, 28-06-2017, BookChapterSeriesAndMatConf
Citation count*0
Cite
Share Share

Get link to the record
msginfo.png


* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back