Dominating sets in planar graphs

Motivated by an application to unstructured multigrid calculations, we consider the problem of asymptotically minimizing the size of dominating sets in triangulated planar graphs. Specifically, we wish to find the smallest epsilon such that, for n sufficiently large, every n-vertex planar graph contains a dominating set of size at most epsilon n. We prove that 1/4 less than or equal to epsilon less than or equal to 1/3, and we conjecture that epsilon = 1/4. For triangulated discs we obtain a tight bound of epsilon = 1/3. The upper bound proof yields a linear-time algorithm for finding an (n/3)-size dominating set.