{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T18:36:47Z","timestamp":1770921407500,"version":"3.50.1"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032178008","type":"print"},{"value":"9783032178015","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-17801-5_39","type":"book-chapter","created":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T17:53:19Z","timestamp":1770918799000},"page":"532-546","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Edge-Constrained Hamiltonian Paths on\u00a0a\u00a0Point Set"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-6521-7987","authenticated-orcid":false,"given":"Todor","family":"Anti\u0107","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0009-0003-3028-4243","authenticated-orcid":false,"given":"Aleksa","family":"D\u017euklevski","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8108-567X","authenticated-orcid":false,"given":"Ji\u0159\u00ed","family":"Fiala","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2620-6133","authenticated-orcid":false,"given":"Jan","family":"Kratochv\u00edl","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2886-9694","authenticated-orcid":false,"given":"Giuseppe","family":"Liotta","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4201-5775","authenticated-orcid":false,"given":"Morteza","family":"Saghafian","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4704-2609","authenticated-orcid":false,"given":"Maria","family":"Saumell","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7398-718X","authenticated-orcid":false,"given":"Johannes","family":"Zink","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,2,13]]},"reference":[{"key":"39_CR1","doi-asserted-by":"publisher","unstructured":"Abellanas, M., Garcia-Lopez, J., Hern\u00e1ndez-Pe\u00f1alver, G., Noy, M., Ramos, P.A.: Bipartite embeddings of trees in the plane. In: North, S.C. (ed.) Proceedings of the 4th International Symposium on Graph Drawing (GD \u201996). Lecture Notes in Computer Science, vol.\u00a01190, pp. 1\u201310. Springer (1996). https:\/\/doi.org\/10.1007\/3-540-62495-3_33","DOI":"10.1007\/3-540-62495-3_33"},{"issue":"2\u20133","key":"39_CR2","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/S0166-218X(99)00042-6","volume":"93","author":"M Abellanas","year":"1999","unstructured":"Abellanas, M., Garcia-Lopez, J., Hern\u00e1ndez-Pe\u00f1alver, G., Noy, M., Ramos, P.A.: Bipartite embeddings of trees in the plane. Discret. Appl. Math. 93(2\u20133), 141\u2013148 (1999). https:\/\/doi.org\/10.1016\/S0166-218X(99)00042-6","journal-title":"Discret. Appl. Math."},{"key":"39_CR3","doi-asserted-by":"publisher","unstructured":"Aichholzer, O., et al.: Packing plane spanning trees and paths in complete geometric graphs. Inf. Process. Lett. 124, 35\u201341 (2017). https:\/\/doi.org\/10.1016\/J.IPL.2017.04.006","DOI":"10.1016\/J.IPL.2017.04.006"},{"key":"39_CR4","unstructured":"Aichholzer, O., et al.: Packing plane spanning trees and paths in complete geometric graphs. In: Proceedings of the 26th Canadian Conference on Computational Geometry (CCCG \u201914), pp. 233\u2013238 (2014). https:\/\/cccg.ca\/proceedings\/2014\/papers\/paper34.pdf"},{"key":"39_CR5","doi-asserted-by":"publisher","unstructured":"Aichholzer, O., et al.: Flipping plane spanning paths. In: Lin, C.C., Lin, B.M.T., Liotta, G. (eds.) Proceedings of the 17th International Conference and Workshops on Algorithms and Computation (WALCOM\u201923), pp. 49\u201360. Springer Nature Switzerland, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-27051-2_5","DOI":"10.1007\/978-3-031-27051-2_5"},{"key":"39_CR6","doi-asserted-by":"publisher","unstructured":"Aichholzer, O., Orthaber, J., Vogtenhuber, B.: Towards crossing-free Hamiltonian cycles in simple drawings of complete graphs. Comput. Geom. Topoloy 3(2), 5:1\u20135:30 (2024). https:\/\/doi.org\/10.57717\/CGT.V3I2.47","DOI":"10.57717\/CGT.V3I2.47"},{"key":"39_CR7","unstructured":"Anti\u0107, T., et al.: Edge-constrained Hamiltonian paths on a point set. arXiv report (2025). https:\/\/arxiv.org\/abs\/2511.22526"},{"key":"39_CR8","doi-asserted-by":"publisher","unstructured":"Bergold, H., Felsner, S., Reddy, M., Orthaber, J., Scheucher, M.: Plane Hamiltonian cycles in convex drawings. Discrete and Computational Geometry (2025). https:\/\/doi.org\/10.1007\/s00454-025-00752-3","DOI":"10.1007\/s00454-025-00752-3"},{"key":"39_CR9","doi-asserted-by":"publisher","unstructured":"Biedl, T., Kindermann, P.: Finding Tutte paths in linear time. In: Baier, C., Chatzigiannakis, I., Flocchini, P., Leonardi, S. (eds.) Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP \u201919). LIPIcs, vol.\u00a0132, pp. 23:1\u201323:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019). https:\/\/doi.org\/10.4230\/LIPICS.ICALP.2019.23","DOI":"10.4230\/LIPICS.ICALP.2019.23"},{"key":"39_CR10","doi-asserted-by":"publisher","unstructured":"Biniaz, A., Bose, P., Maheshwari, A., Smid, M.H.M.: Packing plane perfect matchings into a point set. Discrete Math. Theor. Comput. Sci. 17(2), 119\u2013142 (2015). https:\/\/doi.org\/10.46298\/DMTCS.2132","DOI":"10.46298\/DMTCS.2132"},{"key":"39_CR11","unstructured":"Biniaz, A., Garc\u00eda, A.: Packing plane spanning trees into a point set. In: Durocher, S., Kamali, S. (eds.) Proceedings of the 30th Canadian Conference on Computational Geometry (CCCG\u201918), pp. 49\u201353 (2018). http:\/\/www.cs.umanitoba.ca\/%7Ecccg2018\/papers\/session2A-p1.pdf"},{"key":"39_CR12","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2020.101653","volume":"90","author":"A Biniaz","year":"2020","unstructured":"Biniaz, A., Garc\u00eda, A.: Packing plane spanning trees into a point set. Comput. Geom. 90, 101653 (2020). https:\/\/doi.org\/10.1016\/j.comgeo.2020.101653","journal-title":"Comput. Geom."},{"key":"39_CR13","doi-asserted-by":"publisher","unstructured":"Bose, P., Hurtado, F., Rivera-Campo, E., Wood, D.R.: Partitions of complete geometric graphs into plane trees. In: Pach, J. (ed.) Proceedings of the 12th International Symposium on Graph Drawing (GD \u201904). Lecture Notes in Computer Science, vol.\u00a03383, pp. 71 \u2013 81. Springer (2004). https:\/\/doi.org\/10.1007\/978-3-540-31843-9_9","DOI":"10.1007\/978-3-540-31843-9_9"},{"issue":"2","key":"39_CR14","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1016\/j.comgeo.2005.08.006","volume":"34","author":"P Bose","year":"2006","unstructured":"Bose, P., Hurtado, F., Rivera-Campo, E., Wood, D.R.: Partitions of complete geometric graphs into plane trees. Comput. Geom. 34(2), 116\u2013125 (2006). https:\/\/doi.org\/10.1016\/j.comgeo.2005.08.006","journal-title":"Comput. Geom."},{"key":"39_CR15","doi-asserted-by":"publisher","unstructured":"Hershberger, J., Suri, S.: Applications of a semi-dynamic convex hull algorithm. In: Gilbert, J.R., Karlsson, R.G. (eds.) Proceedings of the 2nd Scandinavian Workshop on Algorithm Theory (SWAT \u201990). Lecture Notes in Computer Science, vol.\u00a0447, pp. 380\u2013392. Springer (1990). https:\/\/doi.org\/10.1007\/3-540-52846-6_106","DOI":"10.1007\/3-540-52846-6_106"},{"issue":"2","key":"39_CR16","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/BF01994880","volume":"32","author":"J Hershberger","year":"1992","unstructured":"Hershberger, J., Suri, S.: Applications of a semi-dynamic convex hull algorithm. BIT 32(2), 249\u2013267 (1992). https:\/\/doi.org\/10.1007\/BF01994880","journal-title":"BIT"},{"issue":"1","key":"39_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00454-017-9921-8","volume":"60","author":"C Keller","year":"2017","unstructured":"Keller, C., Perles, M.A.: Blockers for simple Hamiltonian paths in convex geometric graphs of even order. Discrete Comput. Geom. 60(1), 1\u20138 (2017). https:\/\/doi.org\/10.1007\/s00454-017-9921-8","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"39_CR18","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1007\/s00454-019-00155-1","volume":"65","author":"C Keller","year":"2019","unstructured":"Keller, C., Perles, M.A.: Blockers for simple Hamiltonian paths in convex geometric graphs of odd order. Discrete Comput. Geom. 65(2), 425\u2013449 (2019). https:\/\/doi.org\/10.1007\/s00454-019-00155-1","journal-title":"Discrete Comput. Geom."},{"key":"39_CR19","doi-asserted-by":"publisher","unstructured":"Kindermann, P., Kratochv\u00edl, J., Liotta, G., Valtr, P.: Three edge-disjoint plane spanning paths in a point set. In: Bekos, M.A., Chimani, M. (eds.) Proceedings of the 31st International Symposium on Graph Drawing and Network Visualization (GD \u201923). Lecture Notes in Computer Science, vol. 14465, pp. 323\u2013338. Springer (2023). https:\/\/doi.org\/10.1007\/978-3-031-49272-3_22","DOI":"10.1007\/978-3-031-49272-3_22"},{"key":"39_CR20","doi-asserted-by":"publisher","unstructured":"Kleist, L., Kramer, P., Rieck, C.: On the connectivity of the flip graph of plane spanning paths. In: Kr\u00e1l, D., Milani\u010d, M. (eds.) Proceedings of the 50th International Workshop on Graph-Theoretic Concepts in Computer Science (WG\u201924), pp. 327\u2013342. Springer-Verlag, Berlin, Heidelberg (2024). https:\/\/doi.org\/10.1007\/978-3-031-75409-8_23","DOI":"10.1007\/978-3-031-75409-8_23"},{"key":"39_CR21","doi-asserted-by":"publisher","unstructured":"Pilz, A., Welzl, E.: Order on order types. Discrete Comput. Geom. 59(4), 886\u2013922 (2017). https:\/\/doi.org\/10.1007\/s00454-017-9912-9","DOI":"10.1007\/s00454-017-9912-9"},{"key":"39_CR22","doi-asserted-by":"publisher","unstructured":"Sanders, D.P.: On paths in planar graphs. Journal of Graph Theory 24(4), 341\u2013345 (1997). https:\/\/doi.org\/10.1002\/(sici)1097-0118(199704)24:4<341::aid-jgt6>3.0.co;2-o","DOI":"10.1002\/(sici)1097-0118(199704)24:4<341::aid-jgt6>3.0.co;2-o"},{"key":"39_CR23","doi-asserted-by":"publisher","unstructured":"Schmid, A., Schmidt, J.M.: Computing Tutte paths. In: Chatzigiannakis, I., Kaklamanis, C., Marx, D., Sannella, D. (eds.) Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP \u201918). LIPIcs, vol.\u00a0107, pp. 98:1\u201398:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2018). https:\/\/doi.org\/10.4230\/LIPICS.ICALP.2018.98","DOI":"10.4230\/LIPICS.ICALP.2018.98"},{"key":"39_CR24","doi-asserted-by":"publisher","unstructured":"Thomassen, C.: A theorem on paths in planar graphs. J. Graph Theory 7(2), 169\u2013176 (1983). https:\/\/doi.org\/10.1002\/JGT.3190070205","DOI":"10.1002\/JGT.3190070205"},{"issue":"1","key":"39_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/bf01837870","volume":"15","author":"WT Tutte","year":"1977","unstructured":"Tutte, W.T.: Bridges and Hamiltonian circuits in planar graphs. Aequationes Math. 15(1), 1\u201333 (1977). https:\/\/doi.org\/10.1007\/bf01837870","journal-title":"Aequationes Math."},{"key":"39_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1007\/978-3-540-24595-7_8","volume-title":"Graph Drawing","author":"J \u010cern\u00fd","year":"2004","unstructured":"\u010cern\u00fd, J., Dvo\u0159\u00e1k, Z., Jel\u00ednek, V., K\u00e1ra, J.: Noncrossing Hamiltonian Paths in Geometric Graphs. In: Liotta, G. (ed.) GD 2003. LNCS, vol. 2912, pp. 86\u201397. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-24595-7_8"},{"issue":"9","key":"39_CR27","doi-asserted-by":"publisher","first-page":"1096","DOI":"10.1016\/j.dam.2005.12.010","volume":"155","author":"J \u010cern\u00fd","year":"2007","unstructured":"\u010cern\u00fd, J., Dvo\u0159\u00e1k, Z., Jel\u00ednek, V., K\u00e1ra, J.: Noncrossing Hamiltonian paths in geometric graphs. Discret. Appl. Math. 155(9), 1096\u20131105 (2007). https:\/\/doi.org\/10.1016\/j.dam.2005.12.010","journal-title":"Discret. Appl. Math."}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2026: Theory and Practice of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-17801-5_39","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T17:53:21Z","timestamp":1770918801000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-17801-5_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032178008","9783032178015"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-17801-5_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"13 February 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"SOFSEM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Current Trends in Theory and Practice of Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Krakow","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Poland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 February 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 February 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"51","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sofsem2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sofsem.uj.edu.pl\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}