Parameterized Complexity of 1-Planarity
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 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 NP -complete for graphs of bounded bandwidth, pathwidth, or treewidth., number=1, journal=Journal of Graph Algorithms and Applications, author=Bannister, Michael and Cabello, Sergio and Eppstein, David, year=2018, month=Jan., pages=23–49