{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,4]],"date-time":"2026-07-04T20:57:32Z","timestamp":1783198652347,"version":"3.54.6"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1997,3,1]],"date-time":"1997-03-01T00:00:00Z","timestamp":857174400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[1997,3]]},"DOI":"10.1007\/bf02770871","type":"journal-article","created":{"date-parts":[[2007,12,14]],"date-time":"2007-12-14T09:10:07Z","timestamp":1197623407000},"page":"143-162","source":"Crossref","is-referenced-by-count":23,"title":["On recognizing and characterizing visibility graphs of simple polygons"],"prefix":"10.1007","volume":"17","author":[{"given":"S. K.","family":"Ghosh","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"(3)","key":"BF02770871_CR1","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1007\/BF02570710","volume":"14","author":"J. Abello","year":"1995","unstructured":"J. Abello, O. Egecioglu, and K. Kumar, Visibility graphs of staircase polygons and the weak Bruhat order, I: from visibility graphs to maximal chains,Discrete & Computational Geometry, 14(3) (1995), 331\u2013358.","journal-title":"Discrete & Computational Geometry"},{"key":"BF02770871_CR2","unstructured":"J. Abello, O. Egecioglu, and K. Kumar, Visibility graphs of staircase polygons and the weak Bruhat order, II: from maximal chains to polygons, preprint."},{"key":"BF02770871_CR3","series-title":"Visibility graphs and oriented metroids","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1007\/3-540-58950-3_366","volume-title":"Proceeding of Graph Drawing","author":"J. Abello","year":"1995","unstructured":"J. Abello and K. Kumar, Visibility graphs and oriented metroids,Proceeding of Graph Drawing, Lecture Notes in Computer Science, Vol.894, Springer-Verlag, Berlin, pp. 147\u2013158, 1995."},{"key":"BF02770871_CR4","first-page":"119","volume":"90","author":"J. Abello","year":"1992","unstructured":"J. Abello, H. Lin, and S. Pisupati, On visibility graphs of simple polygons,Congressus Numeratium, 90 (1992), 119\u2013128.","journal-title":"Congressus Numeratium"},{"key":"BF02770871_CR5","doi-asserted-by":"crossref","unstructured":"D. Avis and D. Rappaport, Computing the largest empty convex subset of a set of points,Proceedings of the First ACM Symposium on Computational Geometry, pp. 161-167, 1985.","DOI":"10.1145\/323233.323255"},{"key":"BF02770871_CR6","volume-title":"Ph.D. Dissertation, Report No. NSO-21","author":"M. A. Buckinghan","year":"1980","unstructured":"M. A. Buckinghan, Circle Graphs, Ph.D. Dissertation, Report No. NSO-21, Courant Institute of Mathematical Sciences, New York, 1980."},{"key":"BF02770871_CR7","volume-title":"Hierarchical decomposition of polygons with applications, Ph.D. Dissertation","author":"H. ElGindy","year":"1985","unstructured":"H. ElGindy, Hierarchical decomposition of polygons with applications, Ph.D. Dissertation, McGill University, Montreal, 1985."},{"key":"BF02770871_CR8","unstructured":"H. Everett, Visibility graph recognition, Ph.D. Dissertation, University of Toronto, Toronto, January 1990."},{"key":"BF02770871_CR9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0196-6774(90)90026-B","volume":"11","author":"H. Everett","year":"1990","unstructured":"H. Everett and D. Corneil, Recognizing visibility graphs of spiral polygons,Journal of Algorithms, 11 (1990), 1\u201326.","journal-title":"Journal of Algorithms"},{"key":"BF02770871_CR10","doi-asserted-by":"crossref","unstructured":"C. P. Gabor, W. Hsu, and K. J. Supowit, Recognizing circle graphs in polynomial time,Proceedings of the 26th IEEE Annual Symposium on Foundation of Computer Science, pp. 106-116, 1985.","DOI":"10.1109\/SFCS.1985.47"},{"key":"BF02770871_CR11","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1137\/0201013","volume":"1","author":"F. Gravil","year":"1972","unstructured":"F. Gravil, Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph,SIAM Journal on Computing, 1 (1972), 180\u2013187.","journal-title":"SIAM Journal on Computing"},{"key":"BF02770871_CR12","first-page":"96","volume-title":"On recognizing and characterizing visibility graphs of simple polygons, Report JHU\/EECS-86\/14","author":"S. K. Ghosh","year":"1986","unstructured":"S. K. Ghosh, On recognizing and characterizing visibility graphs of simple polygons, Report JHU\/EECS-86\/14, The Johns Hopkins University, Baltimore, 1986. Also inProceedings of the Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science, Vol.318, Springer-Verlag, Berlin, pp. 96\u2013104, 1988."},{"key":"BF02770871_CR13","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/0925-7721(93)90010-4","volume":"3","author":"S. K. Ghosh","year":"1993","unstructured":"S. K. Ghosh, A. Maheshwari, S. P. Pal, S. Saluja, and C. E. Veni Madhavan, Characterizing and recognizing weak visibility polygons,Computational Geometry: Theory and Applications, 3 (1993), 213\u2013233.","journal-title":"Computational Geometry: Theory and Applications"},{"key":"BF02770871_CR14","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M. C. Golumbic","year":"1980","unstructured":"M. C. Golumbic,Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980."},{"key":"BF02770871_CR15","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/BF01553883","volume":"4","author":"J. Hershberger","year":"1989","unstructured":"J. Hershberger, An optimal visibility graph algorithm for triangulated simple polygon,Algorithmica, 4 (1989), 141\u2013155.","journal-title":"Algorithmica"},{"key":"BF02770871_CR16","doi-asserted-by":"crossref","first-page":"560","DOI":"10.1145\/359156.359164","volume":"22","author":"T. Lazano-Perez","year":"1979","unstructured":"T. Lazano-Perez and M. A. Wesley, An algorithm for planning collision free paths among polygonal obstacles,Communications of the ACM, 22 (1979), 560\u2013570.","journal-title":"Communications of the ACM"},{"key":"BF02770871_CR17","volume-title":"Art Gallery Theorems and Algorithms","author":"J. O\u2019Rourke","year":"1987","unstructured":"J. O\u2019Rourke,Art Gallery Theorems and Algorithms, Oxford University Press, Oxford, 1987."},{"key":"BF02770871_CR18","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1145\/152992.152994","volume":"24","author":"J. O\u2019Rourke","year":"1993","unstructured":"J. O\u2019Rourke, Computational geometry column 18,SIGACT News, 24 (1993), 20\u201325.","journal-title":"SIGACT News"},{"key":"BF02770871_CR19","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1109\/TPAMI.1979.4766871","volume":"1","author":"L. G. Shapiro","year":"1979","unstructured":"L. G. Shapiro and R. M. Haralick, Decomposition of two-dimensional shape by graph-theoretic clustering,IEEE Transactions on Pattern Analysis and Machine Intelligence, 1 (1979), 10\u201319.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"BF02770871_CR20","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BF02239742","volume":"42","author":"T. Shermer","year":"1989","unstructured":"T. Shermer, Hiding people in polygons,Computing, 42 (1989), 109\u2013132.","journal-title":"Computing"},{"key":"BF02770871_CR21","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/BF02574366","volume":"12","author":"G. Srinivasaraghavan","year":"1994","unstructured":"G. Srinivasaraghavan and A. Mukhopadhyay, A new necessary condition for the vertex visibility graphs of simple polygons,Discrete & Computational Geometry, 12 (1994), 65\u201382.","journal-title":"Discrete & Computational Geometry"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02770871.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02770871\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02770871","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T02:02:37Z","timestamp":1558404157000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02770871"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,3]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1997,3]]}},"alternative-id":["BF02770871"],"URL":"https:\/\/doi.org\/10.1007\/bf02770871","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,3]]}}}