Testing Gap k-planarity is NP-complete

John C. Urschel, Jake Wellens

For all $k\ge 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…