On the Complexity of Recognizing Intersection and Touching Graphs of Disks

Breu, Heinz and Kirkpatrick, David G. (1996) On the Complexity of Recognizing Intersection and Touching Graphs of Disks. In: Symposium on Graph Drawing, GD 1995, September 20-22, 1995, Passau, Germany , pp. 88-98 (Official URL: http://dx.doi.org/10.1007/BFb0021793).

Full text not available from this repository.


Disk intersection (respectively, touching) graphs are the inersection graphs of closed disks in the plane whose interiors may (respectively, may not) overlap. In a previous paper [BK93], we showed that the recognition problem for unit disk intersection graphs (i.e. intersection graphs of unit disks) is NP-hard. That proof is easily modified to apply to unit disk touching graphs as well. In this paper, we show how to generalize our earlier construction to accomodate disks whose size may differ. In particular, we prove that the recognition problems for both bounded-ratio disk intersection graphs and bounded-ratio disk touching graphs are also NP-hard. (By bounded-ratio we refer to the natural generalization of the unit constraint in which the radius ratio of the largest to smallest permissible disk is bounded by some fixed constant.) The latter result contrasts with the fact that the disk touching graphs (of unconstrained ratio) are precisely the planar graphs, and are hence polynomial time recognizable. The recognition problem for disk intersection graphs (of unconstrained ratio) has recently been shown to be NP-hard as well [Kra95].

Item Type:Conference Paper
Additional Information:10.1007/BFb0021793
Classifications:G Algorithms and Complexity > G.560 Geometry
Z Theory > Z.250 Geometry
ID Code:50

Repository Staff Only: item control page


Heinz Breu. Algorithmic Aspects of Constrained Unit Disk Graphs. Ph.D.thesis, University of British Columbia, Vancouver, Canada. In preparation.

Sandeep N. Bhatt and Stavros S. Cosmadakis. The complexity of minimizing wire lengths in VLSI layouts. Information Processing Letters, 25(4):263-267, 1987.

Heinz Breu and David G. Kirkpatrick. Unit Disk Graph Recognition is NP-Hard. Technical Report 93-27, Department of Computer Science, University of British Columbia, August, 1993. (To appear in Computational Geometry: Theory and Applications.)

K.S. Booth and G.S. Luecker. Testing for the consecutive ones property, interval graphs and graph planarity using PQ-tree algorithms. J. Comput. System Sci., 13:335-379, 1976.

John Canny. Some algebraic and geometric computations in PSPACE. In Proceedings of the 20th Annual Symposium on the Theory of Computing , pages 460-467, Chicago, Illinois, 2-4 May 1988

Brent N. Clark, Charles J. Colbourn, and David S. Johnson. Unit disk graphs. Discrete Mathematics, 86(1/3):165-177, 1990.

D.R. Fulkerson and O.A. Gross. Incidence matrices and interval graphs. Pacific Journal of Mathematics, 15(3):835-355, 1965.

Peter C. Fishburn. On the sphericity and cubicity of graphs. Journal of Combinatorial Theory, Series B, 35:309-318, 1983.

Michael R. Garey and David S. Johnson. Computers and Intractability: a Guide to the Theory of NP-completeness. W.H. Freeman and Company, 1979.

Albert Gräf. Coloring and Recognizing Special Graph Classes. PhD Thesis, Musikwissenschaftliches Institut, Abteilung Musikinformatik, Johannes Gutenberg-Universität Mainz, February 1995. Available a technical report Bericht Nr. 20.

Wiliam K. Hale. Frequency assignment: theory and applications. Proceedings of the IEEE, 68(12):1497-1514, 1980.

Timothy Franklin Havel. The Combinatorial Distance Geometry Approach to the Calculation of Molecular Conformation. PhD thesis, University of California, Berkeley, 1982. Cited by [Fis83].

David S. Johnson, Cecilia A. Aragon, Lyle.A. McGeogh, and Catherine Schevon. Optimization by simulated annealing: an experimental evaluation; part II, graph coloring and number partioning. Operations Research, 39(3):378-406, May-June 1991.

J. Kratochvíl. String graphs II. Recognizing string graphs is NP-hard. J. Combin. Theory Ser. B, 52:67-78, 1991.

J. Kratochvíl. A special planar satisfiability problem and a consequence of its NP-completeness. Discrete Applied Mathematics, 52: 233-252, 1994.

J. Kratochvíl. Personal communication, February, 1995.

M.V. Marathe, H.B. Hunt III, and S.S. Ravi. Geometry based approximations for intersection graphs. In Fourth Canadian Conference on Computational Geometry, pages 244-249, 10-14 August 1992.

S. Malitz and A. Papakostas. On the angular resolution of planar graphs. In Proceedings of the 24th Annual Symposium on the Theory of Computing, pages 527-538, May 1992.

Fred S. Roberts. Indifference graphs. In Proof Techniques in Graph Theory, pages 139-146, Academic Press, New York and London, February 1968. Proceedings of the Second Ann Arbor Graph Theory Conference.

Fred S. Roberts . Quo Vadis, Graph Theory. Technical Report 91-33, DIMACS, May 1991.

Horst Sachs. Coin graphs, polyhedra, and conformal mapping. Discrete Mathematics, 134: 133-138, 1994.

Jeremy Spinrad. On comparability and permutation graphs. SIAM Journal on Computing, 14(3):658-670, August 1985.