Orthogonal art galleries with holes: a coloring proof of Aggarwal's theorem (Q819180)

Summary: We prove that \(\left\lfloor{n+h\over 4}\right\rfloor\) vertex guards are always sufficient to see the entire interior of an \(n\)-vertex orthogonal polygon \(P\) with an arbitrary number \(h\) of holes provided that there exists a quadrilateralization whose dual graph is a cactus. Our proof is based upon \(4\)-coloring of a quadrilateralization graph, and it is similar to that of \textit{J. Kahn} and others [SIAM J. Algebraic Discrete Methods 4, 194--206 (1983; Zbl 0533.05021)] for orthogonal polygons without holes. Consequently, we provide an alternate proof of Aggarwal's theorem asserting that \(\left\lfloor{n+h\over 4}\right\rfloor\) vertex guards always suffice to cover any \(n\)-vertex orthogonal polygon with \(h \leq 2\) holes.