Recognizing and Drawing IC-planar Graphs

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.

References in corpus (1)

• Parameterized Complexity of 1-Planarity

Cited by in corpus (14)

• An annotated bibliography on 1-planarity
• A Survey on Graph Drawing Beyond Planarity
• Recognizing Optimal 1-Planar Graphs in Linear Time
• Simple $k$-Planar Graphs are Simple $(k+1)$-Quasiplanar
• On Partitioning the Edges of 1-Plane Graphs
• Compact Drawings of 1-Planar Graphs with Right-Angle Crossings and Few Bends
• On Visibility Representations of Non-planar Graphs
• T-Shape Visibility Representations of 1-Planar Graphs
• Drawing Graphs with Circular Arcs and Right-Angle Crossings
• A Note on IC-Planar Graphs
• A Reduction System for Optimal 1-Planar Graphs
• 1-Bend RAC Drawings of 1-Planar Graphs
• New Results on Edge Partitions of 1-plane Graphs
• Extending Partial 1-Planar Drawings