Technical Reports

The ICICS/CS Reading Room


UBC CS TR-93-27 Summary

Unit Disk Graph Recognition is NP-Hard*, August 1993 Heinz Breu and David Kirkpatrick, 22 pages

Unit disk graphs are the intersection graphs of unit diameter closed disks in the plane. This paper reduces SATISFIABILITY to the problem of recognizing unit disk graphs. Equivalently, it shows that determining if a graph has sphericity 2 or less, even if the graph is planar or is known to have sphericity at most 3, is NP-hard. We show how this reduction can be extended to 3 dimensions, thereby showing that unit sphere graph recognition, or determining if a graph has sphericity 3 or less, is also NP-hard. We conjecture that K-sphericity is NP-hard for all fixed K greater than 1.


If you have any questions or comments regarding this page please send mail to help@cs.ubc.ca.