Recognizing and Drawing ICPlanar GraphsBrandenburg, Franz J. and Didimo, Walter and Evans, William S. and Kindermann, Philipp and Liotta, Giuseppe and Montecchiani, Fabrizio (2015) Recognizing and Drawing ICPlanar Graphs. In: Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, September 2426, 2015 , pp. 295308(Official URL: http://dx.doi.org/10.1007/9783319272610_25). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783319272610_25
AbstractICplanar graphs are those graphs that admit a drawing where no two crossed edges share an endvertex and each edge is crossed at most once. They are a proper subfamily of the 1planar graphs. Given an embedded ICplanar graph G with n vertices, we present an O(n)time algorithm that computes a straightline drawing of G in quadratic area, and an O(n^3)time algorithm that computes a straightline drawing of G with rightangle crossings in exponential area. Both these area requirements are worstcase optimal. We also show that it is NPcomplete to test ICplanarity both in the general case and in the case in which a rotation system is fixed for the input graph. Furthermore, we describe a polynomialtime algorithm to test whether a set of matching edges can be added to a triangulated planar graph such that the resulting graph is ICplanar.
Actions (login required)
