Special Issue on Graph Drawing Beyond Planarity
Parameterized Complexity of 1-Planarity
Vol. 22, no. 1, pp. 23-49, 2018. Regular paper.
Abstract We consider the problem of drawing graphs with at most one crossing per edge. These drawings, and the graphs that can be drawn in this way, are called $1$-planar. Finding $1$-planar drawings is known to be ${\mathsf{NP}}$-hard, but we prove that it is fixed-parameter tractable with respect to the vertex cover number, tree-depth, and cyclomatic number. Special cases of these algorithms provide polynomial-time recognition algorithms for $1$-planar split graphs and $1$-planar cographs. However, recognizing $1$-planar graphs remains ${\mathsf{NP}}$-complete for graphs of bounded bandwidth, pathwidth, or treewidth.
Submitted: May 2017.
Reviewed: September 2017.
Revised: October 2017.
Accepted: October 2017.
Final: October 2017.
Published: January 2018.
article (PDF)