Hostname: page-component-78c5997874-xbtfd Total loading time: 0 Render date: 2024-11-20T03:59:15.669Z Has data issue: false hasContentIssue false
  • English
  • Français

Determining the thickness of graphs is NP-hard

Published online by Cambridge University Press:  24 October 2008

Anthony Mansfield
Anthony Mansfield
Affiliation:
Mathematical Institute, Oxford
Get access Rights & Permissions [Opens in a new window]

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.

Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 93 , Issue 1 , January 1983 , pp. 9 - 23
Copyright
Copyright © Cambridge Philosophical Society 1983

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

(1)Beineke, L. W. and Wilson, R. J.Selected topics in graph theory (Academic Press, London, 1978).Google Scholar
(2)Garey, M. R. and Johnson, D. S.Computers and intractability a guide to the theory of NP-completeness (Freeman, San Francisco, 1979).Google Scholar
(3)Holyer, I.The NP-completeness of edge colouring. SIAM J. Comput. 10 (1981), 718–720.CrossRefGoogle Scholar
(4)Hopcroft, J. E. and Tarjan, R. E.Efficient planarity testing. J. Ass. Comput. Mach. 21 (1974), 549–568.CrossRefGoogle Scholar
(5)Lichtenstein, D.Planar formulae and their uses. SIAM J. Comput. 11 (1982), 329–343.CrossRefGoogle Scholar