id: 05014317
dt: j
an: 05014317
au: Żyliński, Paweł
ti: Orthogonal art galleries with holes: a coloring proof of Aggarwal’s
    theorem.
so: Electron. J. Comb. 13, No. 1, Research paper R20, 10 p. (2006).
py: 2006
pu: Prof. André Kündgen, Deptartment of Mathematics, California State
    University San Marcos, San Marcos, CA
la: EN
cc: 
ut: orthogonal polygon; quadrilateralization; vertex guards; dual graph
ci: Zbl 0533.05021
li: emis:journals/EJC/Volume_13/Abstracts/v13i1r20.html
ab: 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 {\it 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 \le 2$ holes.
rv: