{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T11:13:39Z","timestamp":1778498019081,"version":"3.51.4"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,10,25]],"date-time":"2016-10-25T00:00:00Z","timestamp":1477353600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2017,1]]},"DOI":"10.1007\/s00454-016-9831-1","type":"journal-article","created":{"date-parts":[[2016,10,25]],"date-time":"2016-10-25T09:06:43Z","timestamp":1477386403000},"page":"164-178","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":22,"title":["Recognition and Complexity of Point Visibility Graphs"],"prefix":"10.1007","volume":"57","author":[{"given":"Jean","family":"Cardinal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3908-5569","authenticated-orcid":false,"given":"Udo","family":"Hoffmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,10,25]]},"reference":[{"key":"9831_CR1","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1007\/s00454-002-2881-6","volume":"28","author":"J Abello","year":"2002","unstructured":"Abello, J., Kumar, K.: Visibility graphs and oriented matroids. Discrete Comput. Geom. 28, 449\u2013465 (2002)","journal-title":"Discrete Comput. Geom."},{"key":"9831_CR2","doi-asserted-by":"crossref","first-page":"412","DOI":"10.1007\/s00454-015-9714-x","volume":"54","author":"KA Adiprasito","year":"2015","unstructured":"Adiprasito, K.A., Padrol, A., Theran, L.: Universality theorems for inscribed polytopes and Delaunay triangulations. Discrete Comput. Geom. 54, 412\u2013431 (2015)","journal-title":"Discrete Comput. Geom."},{"key":"9831_CR3","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1007\/BF02574701","volume":"6","author":"D Bienstock","year":"1991","unstructured":"Bienstock, D.: Some provably hard crossing number problems. Discrete Comput. Geom. 6, 443\u2013459 (1991)","journal-title":"Discrete Comput. Geom."},{"key":"9831_CR4","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511586507","volume-title":"Oriented Matroids","author":"A Bj\u00f6rner","year":"1999","unstructured":"Bj\u00f6rner, A., Las\u00a0Vergnas, M., Sturmfels, B., White, N., Ziegler, G.M.: Oriented Matroids, 2nd edn. Cambridge University Press, Cambridge (1999)","edition":"2"},{"key":"9831_CR5","doi-asserted-by":"crossref","unstructured":"Canny, J.: Some algebraic and geometric computations in PSPACE. In: STOC, pp. 460\u2013467. ACM, New York (1988)","DOI":"10.1145\/62212.62257"},{"key":"9831_CR6","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry: Algorithms and Applications","author":"M Berg de","year":"2008","unstructured":"de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer, Berlin (2008)","edition":"3"},{"key":"9831_CR7","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1007\/BF02770871","volume":"17","author":"SK Ghosh","year":"1997","unstructured":"Ghosh, S.K.: On recognizing and characterizing visibility graphs of simple polygons. Discrete Comput. Geom. 17, 143\u2013162 (1997)","journal-title":"Discrete Comput. Geom."},{"key":"9831_CR8","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511543340","volume-title":"Visibility Algorithms in the Plane","author":"SK Ghosh","year":"2007","unstructured":"Ghosh, S.K.: Visibility Algorithms in the Plane. Cambridge University Press, Cambridge (2007)"},{"key":"9831_CR9","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1145\/2543581.2543589","volume":"46","author":"SK Ghosh","year":"2013","unstructured":"Ghosh, S.K., Goswami, P.P.: Unsolved problems in visibility graphs of points, segments, and polygons. ACM Comput. Surv. 46, 22 (2013)","journal-title":"ACM Comput. Surv."},{"key":"9831_CR10","doi-asserted-by":"crossref","unstructured":"Ghosh, S.K., Roy, B.: Some results on point visibility graphs. In: WALCOM. LNCS, vol. 8344, pp. 163\u2013175. Springer, Berlin (2014)","DOI":"10.1007\/978-3-319-04657-0_17"},{"key":"9831_CR11","first-page":"639","volume":"3","author":"JE Goodman","year":"1990","unstructured":"Goodman, J.E., Pollack, R., Sturmfels, B.: The intrinsic spread of a configuration in $$\\mathbb{R}^d$$ R d . J. Am. Math. Soc. 3, 639\u2013651 (1990)","journal-title":"J. Am. Math. Soc."},{"key":"9831_CR12","doi-asserted-by":"crossref","unstructured":"Gr\u00fcnbaum, B.: Arrangements and Spreads. Regional Conference Series in Mathematics, vol. 10. AMS, Providence, RI (1972)","DOI":"10.1090\/cbms\/010"},{"key":"9831_CR13","doi-asserted-by":"crossref","unstructured":"Gr\u00fcnbaum, B.: Convex Polytopes. Graduate Texts in Mathematics, vol. 221, 2nd edn. Springer, New York (2003)","DOI":"10.1007\/978-1-4613-0019-9"},{"key":"9831_CR14","doi-asserted-by":"crossref","first-page":"1051","DOI":"10.1016\/S0040-9383(01)00034-9","volume":"41","author":"M Kapovich","year":"2002","unstructured":"Kapovich, M., Millson, J.J.: Universality theorems for configuration spaces of planar linkages. Topology 41, 1051\u20131107 (2002)","journal-title":"Topology"},{"key":"9831_CR15","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1007\/s00454-005-1177-z","volume":"34","author":"J K\u00e1ra","year":"2005","unstructured":"K\u00e1ra, J., P\u00f3r, A., Wood, D.R.: On the chromatic number of the visibility graph of a set of points in the plane. Discrete Comput. Geom. 34, 497\u2013506 (2005)","journal-title":"Discrete Comput. Geom."},{"key":"9831_CR16","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1006\/jctb.1994.1071","volume":"62","author":"J Kratochv\u00edl","year":"1994","unstructured":"Kratochv\u00edl, J., Matou\u0161ek, J.: Intersection graphs of segments. J. Comb. Theory, Ser. B 62, 289\u2013315 (1994)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9831_CR17","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1007\/s00454-010-9320-x","volume":"45","author":"J Kyn\u010dl","year":"2011","unstructured":"Kyn\u010dl, J.: Simple realizability of complete abstract topological graphs in P. Discrete Comput. Geom. 45, 383\u2013399 (2011)","journal-title":"Discrete Comput. Geom."},{"key":"9831_CR18","doi-asserted-by":"crossref","first-page":"560","DOI":"10.1145\/359156.359164","volume":"22","author":"T Lozano-P\u00e9rez","year":"1979","unstructured":"Lozano-P\u00e9rez, T., Wesley, M.A.: An algorithm for planning collision-free paths among polyhedral obstacles. Commun. ACM 22, 560\u2013570 (1979)","journal-title":"Commun. ACM"},{"key":"9831_CR19","first-page":"279","volume":"191","author":"YV Matiyasevich","year":"1970","unstructured":"Matiyasevich, Y.V.: Enumerable sets are diophantine. Dokl. Akad. Nauk SSSR 191, 279\u2013282 (1970)","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"9831_CR20","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1016\/j.jctb.2012.09.004","volume":"103","author":"C McDiarmid","year":"2013","unstructured":"McDiarmid, C., M\u00fcller, T.: Integer realizations of disk and segment graphs. J. Comb. Theory, Ser. B 103, 114\u2013143 (2013)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9831_CR21","doi-asserted-by":"crossref","unstructured":"Mn\u00ebv, N.E.: The universality theorems on the classification problem of configuration varieties and convex polytopes varieties. In: Topology and Geometry\u2014Rohlin Seminar. LNM, pp. 527\u2013543. Springer, Berlin (1988)","DOI":"10.1007\/BFb0082792"},{"key":"9831_CR22","volume-title":"Art Gallery Theorems and Algorithms","author":"J O\u2019Rourke","year":"1987","unstructured":"O\u2019Rourke, J.: Art Gallery Theorems and Algorithms. Oxford University Press, New York (1987)"},{"key":"9831_CR23","doi-asserted-by":"crossref","unstructured":"O\u2019Rourke, J., Streinu, I.: Vertex-edge pseudo-visibility graphs: characterization and recognition. In: SoCG, pp. 119\u2013128. ACM, New York (1997)","DOI":"10.1145\/262839.262915"},{"key":"9831_CR24","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1007\/s00454-012-9446-0","volume":"48","author":"MS Payne","year":"2012","unstructured":"Payne, M.S., P\u00f3r, A., Valtr, P., Wood, D.R.: On the connectivity of visibility graphs. Discrete Comput. Geom. 48, 669\u2013681 (2012)","journal-title":"Discrete Comput. Geom."},{"key":"9831_CR25","first-page":"29","volume":"1","author":"A P\u00f3r","year":"2010","unstructured":"P\u00f3r, A., Wood, D.R.: On visibility and blockers. J. Comput. Geom. 1, 29\u201340 (2010)","journal-title":"J. Comput. Geom."},{"key":"9831_CR26","unstructured":"Roy, B.: Point visibility graph recognition is NP-hard. arXiv:1406.2428 (2014)"},{"key":"9831_CR27","doi-asserted-by":"crossref","unstructured":"Schaefer, M.: Complexity of some geometric and topological problems. In: GD, LNCS, vol. 5849, pp. 334\u2013344. Springer, Berlin (2009)","DOI":"10.1007\/978-3-642-11805-0_32"},{"key":"9831_CR28","volume-title":"Thirty Essays on Geometric Graph Theory","author":"M Schaefer","year":"2012","unstructured":"Schaefer, M.: Realizability of graphs and linkages. In: Pach, J. (ed.) Thirty Essays on Geometric Graph Theory. Springer, Berlin (2012)"},{"key":"9831_CR29","first-page":"531","volume":"4","author":"PW Shor","year":"1991","unstructured":"Shor, P.W.: Stretchability of pseudolines is NP-hard. Appl. Geom. Discrete Math. 4, 531\u2013554 (1991)","journal-title":"Appl. Geom. Discrete Math."},{"key":"9831_CR30","volume-title":"Geometrie der Lage","author":"KGC Staudt","year":"1847","unstructured":"Staudt, K.G.C.: Geometrie der Lage. F. Korn, Nuremberg (1847)"},{"key":"9831_CR31","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/j.comgeo.2004.12.003","volume":"31","author":"I Streinu","year":"2005","unstructured":"Streinu, I.: Non-stretchable pseudo-visibility graphs. Comput. Geom. 31, 195\u2013206 (2005)","journal-title":"Comput. Geom."},{"key":"9831_CR32","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1090\/S0273-0979-1987-15532-7","volume":"17","author":"B Sturmfels","year":"1987","unstructured":"Sturmfels, B.: On the decidability of diophantine problems in combinatorial geometry. Bull. Am. Math. Soc. 17, 121\u2013124 (1987)","journal-title":"Bull. Am. Math. Soc."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-016-9831-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-016-9831-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-016-9831-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,14]],"date-time":"2019-09-14T20:50:32Z","timestamp":1568494232000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-016-9831-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,10,25]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["9831"],"URL":"https:\/\/doi.org\/10.1007\/s00454-016-9831-1","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,10,25]]}}}