A Graph-Coloring Result and Its Consequences for Polygon-Guarding Problems

Abstract

The following graph-coloring result is proved: let G be a 2-connected, bipartite, and plane graph. Then one can triangulate G in such a way that the resulting graph is 3-colorable. Such a triangulation can be computed in $O(n^2 )$ time. This result implies several new upper bounds for polygon guarding problems, including the first nontrivial upper bound for the rectilinear prison yard problem. (1) $\lfloor \frac{n}{3} \rfloor $ vertex guards are sufficient to watch the interior of a rectilinear polygon with holes. (2) $\lfloor \frac{5n}{12} \rfloor + 3$ vertex guards ($\lfloor \frac{n + 4}{3} \rfloor $ point guards) are sufficient to simultaneously watch both the interior and exterior of a rectilinear polygon. Moreover, a new lower bound of $\lfloor \frac{5n}{16} \rfloor $ vertex guards for the rectilinear prison yard problem is shown and proved to be asymptotically tight for the class of orthoconvex polygons.