On the Complexity of Recognizing Intersection and Touching Graphs of DisksBreu, 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 2022, 1995 , pp. 8898(Official URL: http://dx.doi.org/10.1007/BFb0021793). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/BFb0021793
AbstractDisk 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 NPhard. 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 boundedratio disk intersection graphs and boundedratio disk touching graphs are also NPhard. (By boundedratio 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 NPhard as well [Kra95].
Actions (login required)
