Testing k-planarity is NP-complete
John Urschel, Jake Wellens · arXiv (Cornell University) · 2019
For all k >= 1, we show that deciding whether a graph is k-planar is NP-complete, extending the well-known fact that deciding 1-planarity is NP-complete. Furthermore, we show that it is NP-hard to approximate the local crossing number of a graph within a factor of 2-\epsilon. Finally, we present results regarding the non-existence of drawings that simultaneously approximately minimize both the crossing number and local crossing number of a graph.