{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,8]],"date-time":"2025-12-08T03:21:36Z","timestamp":1765164096113,"version":"3.46.0"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T00:00:00Z","timestamp":1761523200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T00:00:00Z","timestamp":1761523200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2212129","DMS-2154347"],"award-info":[{"award-number":["CCF-2212129","DMS-2154347"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2025,12]]},"DOI":"10.1007\/s00373-025-02985-8","type":"journal-article","created":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T14:07:13Z","timestamp":1761574033000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Noncrossing Longest Paths and Cycles"],"prefix":"10.1007","volume":"41","author":[{"given":"Greg","family":"Aloupis","sequence":"first","affiliation":[]},{"given":"Ahmad","family":"Biniaz","sequence":"additional","affiliation":[]},{"given":"Prosenjit","family":"Bose","sequence":"additional","affiliation":[]},{"given":"Jean-Lou","family":"De Carufel","sequence":"additional","affiliation":[]},{"given":"David","family":"Eppstein","sequence":"additional","affiliation":[]},{"given":"Anil","family":"Maheshwari","sequence":"additional","affiliation":[]},{"given":"Saeed","family":"Odak","sequence":"additional","affiliation":[]},{"given":"Michiel","family":"Smid","sequence":"additional","affiliation":[]},{"given":"Csaba D.","family":"T\u00f3th","sequence":"additional","affiliation":[]},{"given":"Pavel","family":"Valtr","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,10,27]]},"reference":[{"issue":"3","key":"2985_CR1","doi-asserted-by":"publisher","first-page":"697","DOI":"10.1137\/S0097539796312721","volume":"29","author":"A Aggarwal","year":"1999","unstructured":"Aggarwal, A., Coppersmith, D., Khanna, S., Motwani, R., Schieber, B.: The angular-metric traveling salesman problem. SIAM J. Comput. 29(3), 697\u2013711 (1999). https:\/\/doi.org\/10.1137\/S0097539796312721","journal-title":"SIAM J. Comput."},{"issue":"1","key":"2985_CR2","doi-asserted-by":"publisher","first-page":"75","DOI":"10.46298\/dmtcs.525","volume":"12","author":"O Aichholzer","year":"2010","unstructured":"Aichholzer, O., Cabello, S., Monroy, R.F., Flores-Pe\u00f1aloza, D., Hackl, T., Huemer, C., Hurtado, F., Wood, D.R.: Edge-removal and non-crossing configurations in geometric graphs. Discrete Math. Theoretical Comput. Sci. 12(1), 75\u201386 (2010). https:\/\/doi.org\/10.46298\/dmtcs.525","journal-title":"Discrete Math. Theoretical Comput. Sci."},{"issue":"4","key":"2985_CR3","doi-asserted-by":"publisher","first-page":"385","DOI":"10.3233\/FI-1995-2245","volume":"22","author":"N Alon","year":"1995","unstructured":"Alon, N., Rajagopalan, S., Suri, S.: Long non-crossing configurations in the plane. Fund. Inform. 22(4), 385\u2013394 (1995). https:\/\/doi.org\/10.3233\/FI-1995-2245","journal-title":"Fund. Inform."},{"issue":"1","key":"2985_CR4","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/S00373-023-02734-9","volume":"40","author":"JL \u00c1lvarez-Rebollar","year":"2024","unstructured":"\u00c1lvarez-Rebollar, J.L., Cravioto-Lagos, J., Mar\u00edn, N., Sol\u00e9-Pi, O.A., Urrutia, J.: Crossing and intersecting families of geometric graphs on point sets. Graph. aCombinatorics 40(1), 17 (2024). https:\/\/doi.org\/10.1007\/S00373-023-02734-9","journal-title":"Graph. aCombinatorics"},{"key":"2985_CR5","unstructured":"\u00c1lvarez-Rebollar, J.L., Cravioto-Lagos, J., Urrutia, J.: Crossing families and self crossing Hamiltonian cycles. In: Abstracts of XVI Encuentros de Geometr\u00eda Computacional, pp.\u00a013, (2015)"},{"issue":"4","key":"2985_CR6","doi-asserted-by":"publisher","first-page":"35:1","DOI":"10.1145\/3478537","volume":"17","author":"H-C An","year":"2021","unstructured":"An, H.-C., Kleinberg, R., Shmoys, D.B.: Approximation algorithms for the bottleneck asymmetric traveling salesman problem. ACM Transactions on Algorithms 17(4), 35:1-35:12 (2021). https:\/\/doi.org\/10.1145\/3478537","journal-title":"ACM Transactions on Algorithms"},{"issue":"2","key":"2985_CR7","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1137\/S0097539797320281","volume":"29","author":"EM Arkin","year":"1999","unstructured":"Arkin, E.M., Chiang, Y.-J., Mitchell, J.S.B., Skiena, S., Yang, T.-C.: On the maximum scatter traveling salesperson problem. SIAM J. Comput. 29(2), 515\u2013544 (1999). https:\/\/doi.org\/10.1137\/S0097539797320281","journal-title":"SIAM J. Comput."},{"issue":"2","key":"2985_CR8","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF01215345","volume":"14","author":"B Aronov","year":"1994","unstructured":"Aronov, B., Erd\u0151s, P., Goddard, W., Kleitman, D.J., Klugerman, M., Pach, J., Schulman, L.J.: Crossing families. Combinatorica 14(2), 127\u2013134 (1994). https:\/\/doi.org\/10.1007\/BF01215345","journal-title":"Combinatorica"},{"issue":"5","key":"2985_CR9","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora, S.: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45(5), 753\u2013782 (1998). https:\/\/doi.org\/10.1145\/290179.290180","journal-title":"J. ACM"},{"key":"2985_CR10","doi-asserted-by":"publisher","unstructured":"Barvinok, A., Gimadi, E.K., Serdyukov, A.I.: The maximum TSP. In: Gutin, G., Punnen, A.P. (eds), The Traveling Salesman Problem and Its Variations, pp. 585\u2013607. Springer, New York, NY, (2007). https:\/\/doi.org\/10.1007\/0-306-48213-4_12","DOI":"10.1007\/0-306-48213-4_12"},{"issue":"5","key":"2985_CR11","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1145\/876638.876640","volume":"50","author":"AI Barvinok","year":"2003","unstructured":"Barvinok, A.I., Fekete, S.P., Johnson, D.S., Tamir, A., Woeginger, G.J., Woodroofe, R.: The geometric maximum traveling salesman problem. J. ACM 50(5), 641\u2013664 (2003). https:\/\/doi.org\/10.1145\/876638.876640","journal-title":"J. ACM"},{"issue":"1","key":"2985_CR12","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/s00454-021-00286-4","volume":"67","author":"A Biniaz","year":"2022","unstructured":"Biniaz, A.: Euclidean bottleneck bounded-degree spanning tree ratios. Discrete Comput. Geom. 67(1), 311\u2013327 (2022). https:\/\/doi.org\/10.1007\/s00454-021-00286-4","journal-title":"Discrete Comput. Geom."},{"key":"2985_CR13","doi-asserted-by":"publisher","first-page":"665","DOI":"10.1007\/s00454-023-00486-0","volume":"72","author":"A Biniaz","year":"2024","unstructured":"Biniaz, A.: Acute tours in the plane. Discrete Comput. Geom. 72, 665\u2013673 (2024). https:\/\/doi.org\/10.1007\/s00454-023-00486-0","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"2985_CR14","doi-asserted-by":"publisher","first-page":"88","DOI":"10.20382\/JOCG.V15I1A4","volume":"15","author":"A Biniaz","year":"2024","unstructured":"Biniaz, A.: Improved bounds for covering paths and trees in the plane. J. Comput. Geom. 15(1), 88\u2013108 (2024). https:\/\/doi.org\/10.20382\/JOCG.V15I1A4","journal-title":"J. Comput. Geom."},{"issue":"4","key":"2985_CR15","doi-asserted-by":"publisher","first-page":"1512","DOI":"10.1007\/S00453-018-0482-X","volume":"81","author":"A Biniaz","year":"2019","unstructured":"Biniaz, A., Bose, P., Crosbie, K., De Carufel, J.-L., Eppstein, D., Maheshwari, A., Smid, M.H.M.: Maximum plane trees in multipartite geometric graphs. Algorithmica 81(4), 1512\u20131534 (2019). https:\/\/doi.org\/10.1007\/S00453-018-0482-X","journal-title":"Algorithmica"},{"key":"2985_CR16","doi-asserted-by":"publisher","DOI":"10.1007\/0-387-29929-7","volume-title":"Research Problems in Discrete Geometry","author":"P Brass","year":"2005","unstructured":"Brass, P., Moser, W.O.J., Pach, J.: Research Problems in Discrete Geometry. Springer, New York, NY (2005). https:\/\/doi.org\/10.1007\/0-387-29929-7"},{"key":"2985_CR17","doi-asserted-by":"publisher","DOI":"10.1145\/3765740","author":"S Cabello","year":"2025","unstructured":"Cabello, S., Hoffmann, M., Klost, K., Mulzer, W., Tkadlec, J.: Long plane trees. ACM Trans. Algorithms (2025). https:\/\/doi.org\/10.1145\/3765740","journal-title":"ACM Trans. Algorithms"},{"issue":"9","key":"2985_CR18","doi-asserted-by":"publisher","first-page":"1096","DOI":"10.1016\/j.dam.2005.12.010","volume":"155","author":"J Cern\u00fd","year":"2007","unstructured":"Cern\u00fd, J., Dvor\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."},{"issue":"2","key":"2985_CR19","doi-asserted-by":"publisher","first-page":"462","DOI":"10.1007\/s00454-013-9563-4","volume":"51","author":"A Dumitrescu","year":"2014","unstructured":"Dumitrescu, A., Gerbner, D., Keszegh, B., T\u00f3th, C.D.: Covering paths for planar point sets. Discrete Comput. Geom. 51(2), 462\u2013484 (2014). https:\/\/doi.org\/10.1007\/s00454-013-9563-4","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"2985_CR20","doi-asserted-by":"publisher","first-page":"P31","DOI":"10.37236\/2356","volume":"19","author":"A Dumitrescu","year":"2012","unstructured":"Dumitrescu, A., Pach, J., T\u00f3th, G.: Drawing Hamiltonian cycles with no large angles. The Electronic Journal of Combinatorics 19(2), P31 (2012). https:\/\/doi.org\/10.37236\/2356","journal-title":"The Electronic Journal of Combinatorics"},{"issue":"4","key":"2985_CR21","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1007\/s00454-010-9277-9","volume":"44","author":"A Dumitrescu","year":"2010","unstructured":"Dumitrescu, A., T\u00f3th, C.D.: Long non-crossing configurations in the plane. Discrete Comput. Geom. 44(4), 727\u2013752 (2010). https:\/\/doi.org\/10.1007\/s00454-010-9277-9","journal-title":"Discrete Comput. Geom."},{"key":"2985_CR22","unstructured":"Fekete, S.P.: Simplicity and hardness of the maximum traveling salesman problem under geometric distances. In: Proceedings of the 10th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 337\u2013345, (1999). URL: http:\/\/dl.acm.org\/citation.cfm?id=314500.314586"},{"key":"2985_CR23","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/S0925-7721(96)00012-0","volume":"8","author":"SP Fekete","year":"1997","unstructured":"Fekete, S.P., Woeginger, G.J.: Angle-restricted tours in the plane. Comput. Geom.: Theory Appl. 8, 195\u2013218 (1997). https:\/\/doi.org\/10.1016\/S0925-7721(96)00012-0","journal-title":"Comput. Geom.: Theory Appl."},{"key":"2985_CR24","doi-asserted-by":"publisher","unstructured":"Garey, M.R., Graham, R.L., Johnson, D.S.: Some NP-complete geometric problems. In: Proceedings of the 8th ACM Symposium on Theory of Computing (STOC), pp. 10\u201322, (1976). https:\/\/doi.org\/10.1145\/800113.803626","DOI":"10.1145\/800113.803626"},{"issue":"3","key":"2985_CR25","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/J.JDA.2008.11.007","volume":"7","author":"M-Y Kao","year":"2009","unstructured":"Kao, M.-Y., Sanghi, M.: An approximation algorithm for a bottleneck traveling salesman problem. J. Discrete Algorithms 7(3), 315\u2013326 (2009). https:\/\/doi.org\/10.1016\/J.JDA.2008.11.007","journal-title":"J. Discrete Algorithms"},{"key":"2985_CR26","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1007\/978-1-4614-0110-0_19","volume-title":"Thirty Essays on Geometric Graph Theory","author":"G K\u00e1rolyi","year":"2013","unstructured":"K\u00e1rolyi, G.: Ramsey-type problems for geometric graphs. In: Pach, J. (ed.) Thirty Essays on Geometric Graph Theory, pp. 371\u2013382. Springer, New York, NY (2013)"},{"issue":"4","key":"2985_CR27","doi-asserted-by":"publisher","first-page":"1298","DOI":"10.1137\/S0097539796309764","volume":"28","author":"JSB Mitchell","year":"1999","unstructured":"Mitchell, J.S.B.: Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, $$k$$-MST, and related problems. SIAM J. Comput. 28(4), 1298\u20131309 (1999). https:\/\/doi.org\/10.1137\/S0097539796309764","journal-title":"SIAM J. Comput."},{"key":"2985_CR28","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2021.107779","volume":"386","author":"J Pach","year":"2021","unstructured":"Pach, J., Rubin, N., Tardos, G.: Planar point sets determine many pairwise crossing segments. Adv. Math. 386, 107779 (2021). https:\/\/doi.org\/10.1016\/j.aim.2021.107779","journal-title":"Adv. Math."},{"issue":"3","key":"2985_CR29","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(77)90012-3","volume":"4","author":"CH Papadimitriou","year":"1977","unstructured":"Papadimitriou, C.H.: The Euclidean traveling salesman problem is NP-complete. Theoret. Comput. Sci. 4(3), 237\u2013244 (1977). https:\/\/doi.org\/10.1016\/0304-3975(77)90012-3","journal-title":"Theoret. Comput. Sci."},{"key":"2985_CR30","doi-asserted-by":"publisher","unstructured":"Stein, C., Wagner, D.P.: Approximation algorithms for the minimum bends traveling salesman problem. In: Proceedings of the 8th International Conference on Integer Programming and Combinatorial Optimization (IPCO), volume 2081 of LNCS, pp. 406\u2013422. Springer, (2001). https:\/\/doi.org\/10.1007\/3-540-45535-3_32","DOI":"10.1007\/3-540-45535-3_32"},{"key":"2985_CR31","doi-asserted-by":"publisher","first-page":"255","DOI":"10.7146\/math.scand.a-11840","volume":"45","author":"H Tverberg","year":"1979","unstructured":"Tverberg, H.: A seperation property of plane convex sets. Math. Scand. 45, 255\u2013260 (1979). https:\/\/doi.org\/10.7146\/math.scand.a-11840","journal-title":"Math. Scand."}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-025-02985-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-025-02985-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-025-02985-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,8]],"date-time":"2025-12-08T03:20:25Z","timestamp":1765164025000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-025-02985-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,27]]},"references-count":31,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["2985"],"URL":"https:\/\/doi.org\/10.1007\/s00373-025-02985-8","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"type":"print","value":"0911-0119"},{"type":"electronic","value":"1435-5914"}],"subject":[],"published":{"date-parts":[[2025,10,27]]},"assertion":[{"value":"10 October 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 October 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 October 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Author G. A. declares they have no financial interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interests"}}],"article-number":"122"}}