{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T08:14:11Z","timestamp":1787386451688,"version":"build-2736575974"},"reference-count":29,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[1989,8]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1137\/0402033","type":"journal-article","created":{"date-parts":[[2005,2,23]],"date-time":"2005-02-23T05:58:14Z","timestamp":1109138294000},"page":"371-392","source":"Crossref","is-referenced-by-count":28,"title":["Perfect Graphs and Orthogonally Convex Covers"],"prefix":"10.1137","volume":"2","author":[{"given":"Rajeev","family":"Motwani","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Arvind","family":"Raghunathan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Huzur","family":"Saran","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,8,8]]},"reference":[{"key":"R1","unstructured":"A. Aggarwal, Ph.D. Thesis, The Art Gallery Theorem: its variations, applications and algorithmic aspects, Department of Electrical Engineering and Computer Science, The Johns Hopkins University, Baltimore, MD, 1984"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/0602026"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/0605018"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1137\/0602042"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804396"},{"key":"R6","unstructured":"B. Chazelle, Ph.D. Thesis, Computational geometry and convexity, Department of Computer Science, Yale University, New Haven, CT, 1980, July"},{"key":"R7","unstructured":"J. Culberson, R. Reckhow, Dent diagrams: a unified approach to polygon covering problems, Technical Report, 87-14, Department of Computing Science, University of Alberta, Edmonton, Alberta, Canada, 1987, July"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"J. Culberson, R. Reckhow, Covering polygons is hard, Proc. 29th IEEE Symposium on Foundations of Computer Science, White Plains, NY, 1988, October 24\u201326","DOI":"10.1109\/SFCS.1988.21976"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61568-9"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(84)80012-1"},{"key":"R11","unstructured":"Michael R. Garey, David S. Johnson, Computers and intractability, W. H. Freeman and Co., San Francisco, Calif., 1979, 53\u201356, A Guide to the Theory of NP-completeness80g:680560411.68039"},{"key":"R12","volume-title":"Algorithmic graph theory and perfect graphs","author":"Golumbic Martin Charles","year":"1980"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579273"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(84)90039-X"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(85)90050-4"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1007\/BF01788689"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-444-87806-9.50012-8"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1137\/0214056"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"J. M. Keil, Minimally covering a horizontally convex orthogonal polygon, Proc. 2nd Annual ACM Symposium on Computational Geometry, Yorktown Heights, New York, Association for Computing Machinery, New York, 1986, 43\u201351, June","DOI":"10.1145\/10515.10520"},{"key":"R20","first-page":"55","volume-title":"Selected topics in graph theory, 2","author":"Lov\u00e1sz L.","year":"1983"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"Rajeev Motwani, Arvind Raghunathan, Huzur Saran, Covering orthogonal polygons with star polygons: the perfect graph approach, Proceedings of the Fourth Annual Symposium on Computational Geometry (Urbana, IL, 1988), ACM, New York, 1988, 211\u2013223, June 6\u201381 213 469","DOI":"10.1145\/73393.73415"},{"key":"R22","volume-title":"Art gallery theorems and algorithms","author":"O'Rourke Joseph","year":"1987"},{"key":"R23","unstructured":"A. Raghunathan, Algorithms for weakly triangulated graphs, J. Algorithms, submitted"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"R. Reckhow, J. Culberson, Covering a simple orthogonal polygon with a minimum number of orthogonally convex polygons, Proc. 3rd Annual ACM Symposium on Computational Geometry, Association for Computing Machinery, New York, 1987, 268\u2013277, June","DOI":"10.1145\/41958.41987"},{"key":"R25","unstructured":"R. Reckhow, Covering orthogonally convex polygons with three orientations of dents, Technical Report, 87-17, Department of Computing Science, University of Alberta, Edmonton, Alberta, Canada, 1987, August"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1137\/0603034"},{"key":"R27","unstructured":"Alexander Schrijver, Theory of linear and integer programming, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons Ltd., Chichester, 1986, 170\u201317188m:900900665.90063"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1137\/0603027"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1983.1056648"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0402033","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:48:17Z","timestamp":1787316497000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0402033"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,8]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1989,8]]}},"alternative-id":["10.1137\/0402033"],"URL":"https:\/\/doi.org\/10.1137\/0402033","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[1989,8]]}}}