On Edge Intersection Graphs of Paths with 2 Bends

Martin Pergel , Paweł Rzążewski


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 - [Charles University]
Martin Pergel,,
, Paweł Rzążewski (FMIS / DIPS)
Paweł Rzążewski,,
- Department of Information Processing Systems
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, GEWERBESTRASSE 11, CHAM, CH-6330, SWITZERLAND, 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.
URL http://link.springer.com/chapter/10.1007/978-3-662-53536-3_18
Languageen angielski
Score (nominal)15
Score sourceconferenceIndex
ScoreMinisterial score = 15.0, 31-01-2020, BookChapterSeriesAndMatConfByConferenceseries
Ministerial score (2013-2016) = 15.0, 31-01-2020, BookChapterSeriesAndMatConfByConferenceseries
Publication indicators Scopus Citations = 5; WoS Citations = 3
Citation count*
Share Share

Get link to the record

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