Determining the thickness of graphs is NP-hard
Anthony Mansfield · Mathematical Proceedings of the Cambridge Philosophical Society · 1983
Abstract The thickness of a graph is a measure of its nonplanarity and has applications in the theory of printed circuits. To determine the thickness of an arbitrary graph is a seemingly intractable problem. This is made precise in this paper where we answer an open problem of Garey and Johnson (2) by proving that it is NP-complete to decide whether a graph has thickness two.