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: 
Server: fubinf.inf.fu-berlin.de
File:   pub/reports/tr-b-93-08.ps.gz
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.