Perfect Graphs and Orthogonally Convex Covers
Rajeev Motwani, Arvind U. Raghunathan, Huzur Saran · SIAM Journal on Discrete Mathematics · 1989
The combinatorial structure of visibility in simple orthogonal polygons is studied. It is shown that the visibility graph of a horizontally or vertically convex polygon is a permutation graph. In general, orthogonal polygons can have concavities (dents) with four possible orientations. In the case where the polygon has three dent orientations, it is shown that the visibility graph is weakly triangulated. Since weakly triangulated graphs are perfect, a polynomial algorithm for this polygon covering problem is obtained. Furthermore, the following duality relationship is obtained. The minimum number of orthogonally convex polygons needed to cover an orthogonal polygon P with at most three dent orientations is equal to the maximum number of points of P, no two of which can be contained together in an orthogonally convex covering polygon. Finally, it shown that in the case of orthogonal polygons with all four dent orientations, the above duality relationship fails to hold.