{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T12:02:37Z","timestamp":1710244957195},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1995,7,1]],"date-time":"1995-07-01T00:00:00Z","timestamp":804556800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1995,7]]},"DOI":"10.1007\/bf01300372","type":"journal-article","created":{"date-parts":[[2005,3,25]],"date-time":"2005-03-25T09:45:54Z","timestamp":1111743954000},"page":"27-51","source":"Crossref","is-referenced-by-count":8,"title":["Characterizing and recognizing the visibility graph of a funnel-shaped polygon"],"prefix":"10.1007","volume":"14","author":[{"given":"Seung-Hak","family":"Choi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sung Yong","family":"Shin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kyung-Yong","family":"Chwa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1007\/BF01840436","volume":"1","author":"T. Asano","year":"1986","unstructured":"T. Asano, T. Asano, L. Guibas, J. Hershberger, and H. Imai, Visibility of disjoint polygons,Algorithmica,1 (1986), 49?63.","journal-title":"Algorithmica"},{"key":"CR2","doi-asserted-by":"crossref","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 Comput. Geom., to appear.","DOI":"10.1007\/BF02570710"},{"key":"CR3","unstructured":"J. Abello, O. Egecioglu, and K. Kumar, Visibility graphs of staircase polygons and the weak Bruhat order, II: From maximal chains to polygons,Discrete Comput. Geom., to appear."},{"key":"CR4","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. V. Aho","year":"1974","unstructured":"A. V. Aho, J. E. Hopcroft, and J. D. Ullman,The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974."},{"issue":"12","key":"CR5","doi-asserted-by":"crossref","first-page":"910","DOI":"10.1109\/TC.1981.1675729","volume":"30","author":"D. Avis","year":"1981","unstructured":"D. Avis and G. T. Toussaint, An optimal algorithm for determining the visibility of a polygon from an edge,IEEE Trans. Comput., 30(12) (1981), 910?914.","journal-title":"IEEE Trans. Comput"},{"key":"CR6","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-349-03521-2","volume-title":"Graph Theory with Applications","author":"J. A. Bondy","year":"1976","unstructured":"J. A. Bondy and U. S. R. Murty,Graph Theory with Applications, Elsevier, New York, 1976."},{"key":"CR7","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1007\/BF02187747","volume":"4","author":"B. Chazelle","year":"1989","unstructured":"B. Chazelle and L. Guibas, Visibility and intersection problems in plane geometry,Discrete Comput. Geom.,4 (1989), 551?581.","journal-title":"Discrete Comput. Geom."},{"key":"CR8","doi-asserted-by":"crossref","unstructured":"C. Coullard and A. Lubiw, Distance visibility graphs,Proc. 7th ACM Symp. on Computational Geometry, 1991, pp. 289?296. To appear inInternat. J. Comput. Geom. Appl.","DOI":"10.1145\/109648.109681"},{"key":"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. G. Corneil, Recognizing visibility graphs of spiral polygons,J. Algorithms,11 (1990), 1?26.","journal-title":"J. Algorithms"},{"key":"CR10","volume-title":"Hierarchical Decomposition of Polygons with Applications, Ph.D. dissertation, School of Computer Science","author":"H. A. ElGindy","year":"1985","unstructured":"H. A. ElGindy, Hierarchical Decomposition of Polygons with Applications, Ph.D. dissertation, School of Computer Science, McGill University, Montreal, 1985."},{"key":"CR11","unstructured":"H. Everett, Visibility Graph Recognition, Ph.D. dissertation, Department of Computer Science, University of Toronto, 1990."},{"key":"CR12","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/BF01840360","volume":"2","author":"L. Guibas","year":"1987","unstructured":"L. Guibas, J. Hershberger, D. Leven, M. Sharir, and R. E. Tarjan, Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons,Algorithmica,2 (1987), 209?233.","journal-title":"Algorithmica"},{"key":"CR13","volume-title":"Tech. Report JHU\/EECS-86\/14","author":"S. K. Ghosh","year":"1986","unstructured":"S. K. Ghosh, On Recognizing and Characterizing Visibility Graphs of Simple Polygons, Tech. Report JHU\/EECS-86\/14, Department of Electrical Engineering and Computer Science, The Johns Hopkins University, Baltimore, MD, 1986. Also as Lecture Notes in Computer Science, Vol. 318, R. Karlsson and A. Lingas, eds., Springer-Verlag, Berlin, 1988."},{"issue":"5","key":"CR14","doi-asserted-by":"crossref","first-page":"888","DOI":"10.1137\/0220055","volume":"20","author":"S. K. Ghosh","year":"1991","unstructured":"S. K. Ghosh and D. M. Mount, An output-sensitive algorithm for computing visibility graphs,SIAM J. Comput., 20(5) (1991), 888?910.","journal-title":"SIAM J. Comput."},{"key":"CR15","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":"CR16","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1016\/0095-8956(85)90050-4","volume":"39","author":"R. B. Hayward","year":"1985","unstructured":"R. B. Hayward, Weakly triangulated graphs,J. Combin. Theory Ser. B,39 (1985), 200?209.","journal-title":"J. Combin. Theory Ser. B"},{"key":"CR17","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 polygons,Algorithmica,4 (1989), 141?155.","journal-title":"Algorithmica"},{"key":"CR18","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1016\/0196-6774(85)90012-4","volume":"6","author":"D. S. Johnson","year":"1985","unstructured":"D. S. Johnson, The NP-completeness column: an ongoing guide,J. Algorithms,6 (1985), 434?451.","journal-title":"J. Algorithms"},{"issue":"3","key":"CR19","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1002\/net.3230140304","volume":"14","author":"D. T. Lee","year":"1984","unstructured":"D. T. Lee and F. P. Preparata, Euclidean shortest paths in the presence of rectilinear barriers,Networks, 14(3) (1984), 393?410.","journal-title":"Networks"},{"key":"CR20","volume-title":"Complexity Aspects of Visibility Graphs, Tech. Report","author":"Y.-L. Lin","year":"1992","unstructured":"Y.-L. Lin and S. S. Skiena, Complexity Aspects of Visibility Graphs, Tech. Report, Department of Computer Science, SUNY, Stony Brook, NY, 1992."},{"key":"CR21","volume-title":"Art Gallery Theorems and Algorithms","author":"J. O'Rourke","year":"1987","unstructured":"J. O'Rourke,Art Gallery Theorems and Algorithms, Oxford University Press, New York, 1987."},{"key":"CR22","volume-title":"Visibility Graphs: a Survey (Computational Geometry Column 18), Tech. Report TR 018","author":"J. O'Rourke","year":"1992","unstructured":"J. O'Rourke, Visibility Graphs: a Survey (Computational Geometry Column 18), Tech. Report TR 018, Department of Computer Science, Smith College, Northampton, MA, 1992. Also asInternat. J. Comput. Geom. Appl. 3 (1993), 109?113, and asSIGACT News 24(1) (1993), 20?25."},{"key":"CR23","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry","author":"F. P. Preparata","year":"1985","unstructured":"F. P. Preparata and M. I. Shamos,Computational Geometry, Springer-Verlag, New York, 1985."},{"key":"CR24","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1016\/0167-8655(86)90043-7","volume":"4","author":"G. T. Toussaint","year":"1986","unstructured":"G. T. Toussaint, A linear-time algorithm for solving the strong hidden-line problem in a simple polygon,Pattern Recognition Lett.,4 (1986), 449?451.","journal-title":"Pattern Recognition Lett."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01300372.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01300372\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01300372","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,30]],"date-time":"2019-04-30T18:08:19Z","timestamp":1556647699000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01300372"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,7]]},"references-count":24,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1995,7]]}},"alternative-id":["BF01300372"],"URL":"https:\/\/doi.org\/10.1007\/bf01300372","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,7]]}}}