Recognizing and drawing IC-planar graphs

We give new results about the relationship between 1-planar graphs and RACgraphs. A graph is 1-planar if it has a drawing where each edge is crossed at most once. A graph is RAC if it can be drawn in such a way that its edges cross only at right angles. These two classes of graphs and their relation...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2016-07, Vol.636, p.1-16
Main Authors: Brandenburg, Franz J., Didimo, Walter, Evans, William S., Kindermann, Philipp, Liotta, Giuseppe, Montecchiani, Fabrizio
Format: Article
Language:English
Subjects:
1-planarity
Algorithms
Design analysis
Design engineering
Graph drawing
Graph theory
Graphs
IC-planarity
Matching
NP-hardness
Planes
Right angle crossings
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We give new results about the relationship between 1-planar graphs and RACgraphs. A graph is 1-planar if it has a drawing where each edge is crossed at most once. A graph is RAC if it can be drawn in such a way that its edges cross only at right angles. These two classes of graphs and their relationships have been widely investigated in the last years, due to their relevance in application domains where computing readable graph layouts is important to analyze or design relational data sets. We study IC-planar graphs, the sub-family of 1-planar graphs that admit 1-planar drawings with independent crossings (i.e., no two crossed edges share an endpoint). We prove that every IC-planar graph admits a straight-line RAC drawing, which may require however exponential area. If we do not require right angle crossings, we can draw every IC-planar graph with straight-line edges in linear time and quadratic area. We then study the problem of testing whether a graph is IC-planar. We prove that this problem is NP-hard, even if a rotation system for the graph is fixed. On the positive side, we describe a polynomial-time algorithm that tests whether a triangulated plane graph augmented with a given set of edges that form a matching is IC-planar.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2016.04.026