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 Pages 207-219 Publication size in sheets 0.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 English geometric intersection graphs, bend graphs, bend number Abstract in Polish Reprezentacją 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. DOI DOI:10.1007/978-3-662-53536-3_18 URL http://link.springer.com/chapter/10.1007/978-3-662-53536-3_18 Language en angielski Score (nominal) 15 Score Ministerial score = 15.0, 28-06-2017, BookChapterSeriesAndMatConfMinisterial score (2013-2016) = 15.0, 28-06-2017, BookChapterSeriesAndMatConf Citation count* 0
Cite

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