Logo der Fakultät Logo LG Theoretische Informatik
 

Veröffentlichung

Titel:

Recognizing and Drawing IC-Planar Graphs

AutorInnen: Franz J. Brandenburg
Walter Didimo
William S. Evans
Philipp Kindermann
Giuseppe Liotta
Fabrizio Montecchiani
Kategorie: Konferenzbandbeiträge
erschienen in: Proceedings of the 23rd International Symposium on Graph Drawing and Network Visualization (GD'15), pp. 295-308
Abstract:

IC-planar graphs are those graphs that admit a drawing where no two crossed edges share an end-vertex and each edge is crossed at most once. They are a proper subfamily of the 1-planar graphs. Given an embedded IC-planar graph G with n vertices, we present an O(n)-time algorithm that computes a straight-line drawing of G in quadratic area, and an O(n3)-time algorithm that computes a straight-line drawing of G with right-angle crossings in exponential area. Both these area requirements are worst-case optimal. We also show that it is NP-complete to test IC-planarity both in the general case and in the case in which a rotation system is fixed for the input graph. Furthermore, we describe a polynomial-time algorithm to test whether a set of matching edges can be added to a triangulated planar graph such that the resulting graph is IC-planar.

Download: Proceeding Website
BibTeX-Eintrag: @InProceedings{BDEKLM15, Title = {Recognizing and Drawing IC-Planar Graphs}, Author = {Franz J. Brandenburg and Walter Didimo and William S. Evans and Philipp Kindermann and Giuseppe Liotta and Fabrizio Montecchiani}, Booktitle = {Proceedings of the 23rd International Symposium on Graph Drawing and Network Visualization (GD'15)}, Year = {2015}, Editor = {Emilio Di Giacomo and Anna Lubiw}, Pages = {295--308}, Publisher = {Springer}, Series = {Lecture Notes in Computer Science}, Volume = {9411}, Abstract = {IC-planar graphs are those graphs that admit a drawing where no two crossed edges share an end-vertex and each edge is crossed at most once. They are a proper subfamily of the 1-planar graphs. Given an embedded IC-planar graph $G$ with $n$ vertices, we present an $O(n)$-time algorithm that computes a straight-line drawing of $G$ in quadratic area, and an $O(n^3)$-time algorithm that computes a straight-line drawing of $G$ with right-angle crossings in exponential area. Both these area requirements are worst-case optimal. We also show that it is NP-complete to test IC-planarity both in the general case and in the case in which a rotation system is fixed for the input graph. Furthermore, we describe a polynomial-time algorithm to test whether a set of matching edges can be added to a triangulated planar graph such that the resulting graph is IC-planar.}, Doi = {10.1007/978-3-319-27261-0_25} }
Christoph Doppelbauer | 22.11.2016
FernUni-Logo FernUniversität in Hagen, LG Theoretische Informatik, 58084 Hagen