Recognizing and Drawing IC-Planar Graphs

Brandenburg, Franz J. and Didimo, Walter and Evans, William S. and Kindermann, Philipp and Liotta, Giuseppe and Montecchiani, Fabrizio (2015) Recognizing and Drawing IC-Planar Graphs. In: Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, September 24-26, 2015 , pp. 295-308(Official URL: http://dx.doi.org/10.1007/978-3-319-27261-0_25).

Full text not available from this repository.

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.

Item Type: Conference Paper
Classifications: G Algorithms and Complexity > G.420 Crossings
G Algorithms and Complexity > G.770 Planarity Testing
P Styles > P.540 Planar
P Styles > P.720 Straight-line
Divisions: UNSPECIFIED
Depositing User: Administration GDEA
Date Deposited: 04 May 2016 16:05
Last Modified: 04 May 2016 16:05
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1497

Actions (login required)

View Item View Item