Parameterized Complexity of 1-Planarity

Authors

  • Michael Bannister
  • Sergio Cabello
  • David Eppstein

DOI:

https://doi.org/10.7155/jgaa.00457

Keywords:

1-planar graphs , split graphs , cographs , parameterized complexity , fixed-parameter tractability , kernelization , vertex cover number , tree-depth , cyclomatic number , graph bandwidth , NP-completeness

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.

Downloads

Download data is not yet available.

Downloads

Published

2018-01-01

How to Cite

Bannister, M., Cabello, S., & Eppstein, D. (2018). Parameterized Complexity of 1-Planarity. Journal of Graph Algorithms and Applications, 22(1), 23–49. https://doi.org/10.7155/jgaa.00457