Rajeev Motwani, Arvind Raghunathan and Huzur Saran

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-88-395
December 1987

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1988/CSD-88-395.pdf

We consider the problem of covering simple orthogonal polygons with convex orthogonal polygons. In the case of horizontally or vertically convex polygons we show that the polygon covering problem can be reduced to the problem of covering a permutation graph with minimum number of cliques.

In general, orthogonal polygons can have concavities (dents) with four possible orientations. In the case where the polygon has three dent orientations, we show that the polygon covering problem can be reduced to the problem of covering a weakly triangulated graph with a minimum number of cliques. Since weakly triangulated graphs are perfect, we obtain the following duality relationship: 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, we show that in the case of orthogonal polygons with all four dent orientations, the above duality relationship fails to hold.

BibTeX citation:

@techreport{Motwani:CSD-88-395,
    Author = {Motwani, Rajeev and Raghunathan, Arvind and Saran, Huzur},
    Title = {Perfect Graphs and Orthogonally Convex Covers},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1987},
    Month = {Dec},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1987/5857.html},
    Number = {UCB/CSD-88-395},
    Abstract = {We consider the problem of covering simple orthogonal polygons with convex orthogonal polygons. In the case of horizontally or vertically convex polygons we show that the polygon covering problem can be reduced to the problem of covering a permutation graph with minimum number of cliques. <p>In general, orthogonal polygons can have concavities (dents) with four possible orientations. In the case where the polygon has three dent orientations, we show that the polygon covering problem can be reduced to the problem of covering a weakly triangulated graph with a minimum number of cliques. Since weakly triangulated graphs are perfect, we obtain the following duality relationship: the minimum number of orthogonally convex polygons needed to cover an orthogonal polygon <i>P</i> with at most three dent orientations is equal to the maximum number of points of <i>P</i>, no two of which can be contained together in an orthogonally convex covering polygon. <p>Finally, we show that in the case of orthogonal polygons with all four dent orientations, the above duality relationship fails to hold.}
}

EndNote citation:

%0 Report
%A Motwani, Rajeev
%A Raghunathan, Arvind
%A Saran, Huzur
%T Perfect Graphs and Orthogonally Convex Covers
%I EECS Department, University of California, Berkeley
%D 1987
%@ UCB/CSD-88-395
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1987/5857.html
%F Motwani:CSD-88-395