zbMATH — the first resource for mathematics

Orthogonal art galleries with holes: a coloring proof of Aggarwal’s theorem. (English) Zbl 1087.05020
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 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.

05C15 Coloring of graphs and hypergraphs
05C90 Applications of graph theory
Zbl 0533.05021
Full Text: EuDML EMIS