{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T02:31:41Z","timestamp":1771036301574,"version":"3.50.1"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,1,31]],"date-time":"2022-01-31T00:00:00Z","timestamp":1643587200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,31]],"date-time":"2022-01-31T00:00:00Z","timestamp":1643587200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1422311"],"award-info":[{"award-number":["CCF-1422311"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1423615"],"award-info":[{"award-number":["CCF-1423615"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002790","name":"Canadian Network for Research and Innovation in Machining Technology, Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002790","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001700","name":"Ministry of Education, Culture, Sports, Science and Technology","doi-asserted-by":"publisher","award":["KAKENHI No. 17K12635"],"award-info":[{"award-number":["KAKENHI No. 17K12635"]}],"id":[{"id":"10.13039\/501100001700","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2022,7]]},"DOI":"10.1007\/s00454-021-00355-8","type":"journal-article","created":{"date-parts":[[2022,1,31]],"date-time":"2022-01-31T15:02:58Z","timestamp":1643641378000},"page":"218-254","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Circumscribing Polygons and Polygonizations for Disjoint Line Segments"],"prefix":"10.1007","volume":"68","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6827-2200","authenticated-orcid":false,"given":"Hugo A.","family":"Akitaya","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matias","family":"Korman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Oliver","family":"Korten","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mikhail","family":"Rudoy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Diane L.","family":"Souvaine","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Csaba D.","family":"T\u00f3th","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,1,31]]},"reference":[{"issue":"1","key":"355_CR1","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/j.dam.2007.08.033","volume":"156","author":"PK Agarwal","year":"2008","unstructured":"Agarwal, P.K., Hurtado, F., Toussaint, G.T., Trias, J.: On polyhedra induced by point sets in space. Discrete Appl. Math. 156(1), 42\u201354 (2008)","journal-title":"Discrete Appl. Math."},{"key":"355_CR2","unstructured":"Akitaya, H.A., Korman, M., Rudoy, M., Souvaine, D.L., T\u00f3th, C.D.: Circumscribing polygons and polygonizations for disjoint line segments. In: 35th International Symposium on Computational Geometry (Portland 2019). Leibniz Int. Proc. Inform., vol.\u00a0129, #\u00a09. Leibniz-Zent. Inform., Wadern (2019)"},{"issue":"2","key":"355_CR3","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1016\/j.comgeo.2012.02.008","volume":"46","author":"G Barequet","year":"2013","unstructured":"Barequet, G., Benbernou, N., Charlton, D., Demaine, E.D., Demaine, M.L., Ishaque, M., Lubiw, A., Schulz, A., Souvaine, D.L., Toussaint, G.T., Winslow, A.: Bounded-degree polyhedronization of point sets. Comput. Geom. 46(2), 148\u2013153 (2013)","journal-title":"Comput. Geom."},{"key":"355_CR4","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1016\/j.comgeo.2017.06.001","volume":"68","author":"J Cardinal","year":"2018","unstructured":"Cardinal, J., Hoffmann, M., Kusters, V., T\u00f3th, C.D., Wettstein, M.: Arc diagrams, flip distances, and Hamiltonian triangulations. Comput. Geom. 68, 206\u2013225 (2018)","journal-title":"Comput. Geom."},{"issue":"2","key":"355_CR5","doi-asserted-by":"publisher","first-page":"243","DOI":"10.7155\/jgaa.00257","volume":"16","author":"EW Chambers","year":"2012","unstructured":"Chambers, E.W., Eppstein, D., Goodrich, M.T., L\u00f6ffler, M.: Drawing graphs in the plane with a prescribed outer face and polynomial area. J. Graph Algorithms Appl. 16(2), 243\u2013259 (2012)","journal-title":"J. Graph Algorithms Appl."},{"issue":"2","key":"355_CR6","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/0196-6774(89)90012-6","volume":"10","author":"N Chiba","year":"1989","unstructured":"Chiba, N., Nishizeki, T.: The Hamiltonian cycle problem is linear-time solvable for $$4$$-connected planar graphs. J. Algorithms 10(2), 187\u2013211 (1989)","journal-title":"J. Algorithms"},{"key":"355_CR7","doi-asserted-by":"crossref","unstructured":"Di Giacomo, E., Liotta, G.: The Hamiltonian augmentation problem and its applications to graph drawing. In: 4th International Workshop Algorithms and Computation (WALCOM) (Dhaka 2010). Lecture Notes in Computer Science, vol. 5942, pp. 35\u201346. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-11440-3_4"},{"issue":"4","key":"355_CR8","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/S0925-7721(00)00010-9","volume":"16","author":"A Garc\u00eda","year":"2000","unstructured":"Garc\u00eda, A., Noy, M., Tejel, J.: Lower bounds on the number of crossing-free subgraphs of $$K_N$$. Comput. Geom. 16(4), 211\u2013221 (2000)","journal-title":"Comput. Geom."},{"issue":"4","key":"355_CR9","doi-asserted-by":"publisher","first-page":"704","DOI":"10.1137\/0205049","volume":"5","author":"MR Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Tarjan, R.E.: The planar Hamiltonian circuit problem is NP-complete. SIAM J. Comput. 5(4), 704\u2013714 (1976)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"355_CR10","first-page":"83","volume":"3","author":"B Gr\u00fcnbaum","year":"1994","unstructured":"Gr\u00fcnbaum, B.: Hamiltonian polygons and polyhedra. Geombinatorics 3(3), 83\u201389 (1994)","journal-title":"Geombinatorics"},{"issue":"1","key":"355_CR11","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/S0925-7721(02)00172-4","volume":"26","author":"M Hoffmann","year":"2003","unstructured":"Hoffmann, M., T\u00f3th, C.D.: Segment endpoint visibility graphs are Hamiltonian. Comput. Geom. 26(1), 47\u201368 (2003)","journal-title":"Comput. Geom."},{"key":"355_CR12","doi-asserted-by":"crossref","unstructured":"Hurtado, F., T\u00f3th, C.D.: Plane geometric graph augmentation: a generic perspective. In: Thirty Essays on Geometric Graph Theory, pp. 327\u2013354. Springer, New York (2013)","DOI":"10.1007\/978-1-4614-0110-0_17"},{"issue":"1","key":"355_CR13","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/s00454-012-9466-9","volume":"49","author":"M Ishaque","year":"2013","unstructured":"Ishaque, M., Souvaine, D.L., T\u00f3th, C.D.: Disjoint compatible geometric matchings. Discrete Comput. Geom. 49(1), 89\u2013131 (2013)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"355_CR14","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/0925-7721(92)90018-N","volume":"2","author":"A Mirzaian","year":"1992","unstructured":"Mirzaian, A.: Hamiltonian triangulations and circumscribing polygons of disjoint line segments. Comput. Geom. 2(1), 15\u201330 (1992)","journal-title":"Comput. Geom."},{"issue":"4","key":"355_CR15","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0925-7721(94)90019-1","volume":"4","author":"J O\u2019Rourke","year":"1994","unstructured":"O\u2019Rourke, J., Rippel, J.: Two segment classes with Hamiltonian visibility graphs. Comput. Geom. 4(4), 209\u2013218 (1994)","journal-title":"Comput. Geom."},{"issue":"9","key":"355_CR16","doi-asserted-by":"publisher","first-page":"2646","DOI":"10.1016\/j.disc.2018.06.015","volume":"341","author":"K Ozeki","year":"2018","unstructured":"Ozeki, K., Van Cleemput, N., Zamfirescu, C.T.: Hamiltonian properties of polyhedra with few 3-cuts\u2014a survey. Discrete Math. 341(9), 2646\u20132660 (2018)","journal-title":"Discrete Math."},{"issue":"2","key":"355_CR17","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/S0925-7721(97)00023-0","volume":"10","author":"J Pach","year":"1998","unstructured":"Pach, J., Rivera-Campo, E.: On circumscribing polygons for line segments. Comput. Geom. 10(2), 121\u2013124 (1998)","journal-title":"Comput. Geom."},{"issue":"6","key":"355_CR18","doi-asserted-by":"publisher","first-page":"1128","DOI":"10.1137\/0218075","volume":"18","author":"D Rappaport","year":"1989","unstructured":"Rappaport, D.: Computing simple circuits from a set of line segments is NP-complete. SIAM J. Comput. 18(6), 1128\u20131139 (1989)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"355_CR19","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/BF02187791","volume":"5","author":"D Rappaport","year":"1990","unstructured":"Rappaport, D., Imai, H., Toussaint, G.T.: Computing simple circuits from a set of line segments. Discrete Comput. Geom. 5(3), 289\u2013304 (1990)","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"355_CR20","doi-asserted-by":"publisher","first-page":"777","DOI":"10.1016\/j.jcta.2013.01.002","volume":"120","author":"M Sharir","year":"2013","unstructured":"Sharir, M., Sheffer, A., Welzl, E.: Counting plane graphs: perfect matchings, spanning cycles, and Kasteleyn\u2019s technique. J. Combin. Theory Ser. A 120(4), 777\u2013794 (2013)","journal-title":"J. Combin. Theory Ser. A"},{"key":"355_CR21","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1112\/plms\/s3-10.1.304","volume":"10","author":"WT Tutte","year":"1960","unstructured":"Tutte, W.T.: Convex representations of graphs. Proc. Lond. Math. Soc. 10, 304\u2013320 (1960)","journal-title":"Proc. Lond. Math. Soc."},{"issue":"1","key":"355_CR22","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/0925-7721(92)90020-S","volume":"2","author":"M Urabe","year":"1992","unstructured":"Urabe, M., Watanabe, M.: On a counterexample to a conjecture of Mirzaian. Comput. Geom. 2(1), 51\u201353 (1992)","journal-title":"Comput. Geom."},{"issue":"2","key":"355_CR23","doi-asserted-by":"publisher","first-page":"378","DOI":"10.2307\/1968197","volume":"32","author":"H Whitney","year":"1931","unstructured":"Whitney, H.: A theorem on graphs. Ann. Math. 32(2), 378\u2013390 (1931)","journal-title":"Ann. Math."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-021-00355-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-021-00355-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-021-00355-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,26]],"date-time":"2022-05-26T18:13:36Z","timestamp":1653588816000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-021-00355-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,31]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["355"],"URL":"https:\/\/doi.org\/10.1007\/s00454-021-00355-8","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,31]]},"assertion":[{"value":"29 July 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 July 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 August 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 January 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}