Elsevier

Discrete Mathematics

Volume 86, Issues 1–3, 14 December 1990, Pages 165-177
Discrete Mathematics

Unit disk graphs

https://doi.org/10.1016/0012-365X(90)90358-OGet rights and content
Under an Elsevier user license
open archive

Abstract

Unit disk graphs are the intersection graphs of equal sized circles in the plane: they provide a graph-theoretic model for broadcast networks (cellular networks) and for some problems in computational geometry. We show that many standard graph theoretic problems remain NP-complete on unit disk graphs, including coloring, independent set, domination, independent domination, and connected domination; NP-completeness for the domination problem is shown to hold even for grid graphs, a subclass of unit disk graphs. In contrast, we give a polynomial time algorithm for finding cliques when the geometric representation (circles in the plane) is provided.

Cited by (0)