We consider the problem of finding a 1-planar drawing for a general graph, where a 1-planar drawing is a drawing in which each edge participates in at most one crossing. Since this problem is known to be NP-hard we investigate the parameterized complexity of the problem with respect to the vertex cover number, tree-depth, and cyclomatic number. For these parameters we construct fixed-parameter tractable algorithms. However, the problem remains NP-complete for graphs of bounded bandwidth, pathwidth, or treewidth.
However, without restriction to book drawings, computing local crossing number is NP-hard even for graphs of bounded treewidth REF .
Parameterized Complexity of 1-Planarity
J. Graph Algorithms and Applications 22 (1): 23-49, 2018
Mathematics Computer Science