Perfect Graphs and Orthogonally Convex Covers
Authors:
- Huzur SaranHSHuzur Saran
- 1 August 1989
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 2 (3) , 371-392
Abstract
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.Keywords
This publication has 19 references indexed in Scilit:
- Optimizing weakly triangulated graphsGraphs and Combinatorics, 1989
- Algorithms in Combinatorial Geometry1987
- Weakly triangulated graphsJournal of Combinatorial Theory, Series B, 1985
- An algorithm for covering polygons with rectanglesInformation and Control, 1984
- A minimax theorem on intervalsJournal of Combinatorial Theory, Series B, 1984
- It’s Hard to Color AntirectanglesSIAM Journal on Algebraic Discrete Methods, 1984
- Covering Regions by RectanglesSIAM Journal on Algebraic Discrete Methods, 1981
- Covering Regions with SquaresSIAM Journal on Algebraic Discrete Methods, 1981
- The ellipsoid method and its consequences in combinatorial optimizationCombinatorica, 1981
- Decomposing a polygon into its convex parts1979