Graph Coloring Result and Its Consequences For Polygon Guarding Problems

Frank Hoffmann Klaus Kriegel Institut für Informatik Freie Universität Berlin Report B 93-08 June 1993

Get the report here or by anonymous ftp: 
File:   pub/reports/
We prove the following graph coloring result: Let G be a 2-connected bipartite planar graph. Then one can triangulate G in such a way that the resulting graph is 3-coloring.
This result implies several new upper bounds for guarding problems including the first non-trivial upper bound for the rectilinear Prison Yard Problem:

1. $[\frac{n}{3}]$ vertex guards are sufficient to watch the interior of a rectilinear polygon with holes.
2. $[\frac{5n}{12}]+3$ vertex guards resp. $[\frac{n+4}{3}]$ point guards are sufficient to watch simultaneously both the interior and exterior of a rectilinear polygon.

Moreover, we show a new lower bound of $[\frac{5n}{16}]$ vertex guards for the rectilinear Prison Yard Problem and prove it to be asymptotically tight for the class of othoconvex polygons.