Parameterized Complexity of 1-Planarity - Bannister, Michael; Cabello, Sergio; Eppstein, David (Journal of Graph Algorithms and Applications, 2018)
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.