Square roots of nearly planar graphs

Zdeněk Dvořák, Benjamin Moore, Abhiruk Lahiri

We prove that it is NP-hard to decide whether a graph is the square of a 6-apex graph. This shows that the square root problem is not tractable for squares of sparse graphs (or eve…