SIMPLE HEURISTICS FOR UNIT DISK GRAPHS

Unit disk graphs are intersection graphs of circles of unit radius in the plane. We present simple and provably good heuristics for a number of classical NP-hard optimization problems on unit disk graphs. The p roblems considered include maximum independent set, minimum vertex cov er, minimum coloring, and minimum dominating set. We also present an o n-line coloring heuristic which achieves a competitive ratio of 6 for unit disk graphs. Our heuristics do not need a geometric representatio n of unit disk graphs. Geometric representations are used only in esta blishing the performance guarantees of the heuristics. Several of our approximation algorithms can be extended to intersection graphs of cir cles of arbitrary radii in the plane, intersection graphs of regular p olygons, and intersection graphs of higher dimensional regular objects . (C) 1995 John Wiley and Sons, Inc.