Determining the thickness of graphs is NP-hard
- 1 January 1983
- journal article
- research article
- Published by Cambridge University Press (CUP) in Mathematical Proceedings of the Cambridge Philosophical Society
- Vol. 93 (1) , 9-23
- https://doi.org/10.1017/s030500410006028x
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.Keywords
This publication has 3 references indexed in Scilit:
- Planar Formulae and Their UsesSIAM Journal on Computing, 1982
- The NP-Completeness of Edge-ColoringSIAM Journal on Computing, 1981
- Efficient Planarity TestingJournal of the ACM, 1974