{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,8]],"date-time":"2025-12-08T06:51:07Z","timestamp":1765176667925,"version":"build-2065373602"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"1","funder":[{"DOI":"10.13039\/501100004329","name":"Slovenian Research Agency","doi-asserted-by":"crossref","award":["P1-0297, J1-9109, J1-8130, J1-8155, J1-1693, J1-2452, N1-0218, N1-0285"],"award-info":[{"award-number":["P1-0297, J1-9109, J1-8130, J1-8155, J1-1693, J1-2452, N1-0218, N1-0285"]}],"id":[{"id":"10.13039\/501100004329","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000780","name":"European Union","doi-asserted-by":"crossref","award":["101071836"],"award-info":[{"award-number":["101071836"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001711","name":"Swiss National Science Foundation","doi-asserted-by":"crossref","award":["200021E-171681"],"award-info":[{"award-number":["200021E-171681"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]},{"name":"ERC StG","award":["757609"],"award-info":[{"award-number":["757609"]}]},{"name":"Charles Univ. projects","award":["UNCE 24\/SCI\/008 and PRIMUS 24\/SCI\/012"],"award-info":[{"award-number":["UNCE 24\/SCI\/008 and PRIMUS 24\/SCI\/012"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2026,1,31]]},"abstract":"<jats:p>\n            In the\n            <jats:italic toggle=\"yes\">longest plane spanning tree<\/jats:italic>\n            problem, we are given a finite planar point set\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathcal{P}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            , and our task is to find a plane (i.e., noncrossing) spanning tree for\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathcal{P}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            with maximum total Euclidean edge length. Despite more than two decades of research, it remains open whether this problem is NP-hard. Thus, previous results have focused on polynomial-time algorithms that produce plane trees whose total edge length approximates\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathrm{OPT}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            , the maximum possible length. The approximate trees in these algorithms all have small unweighted diameter, typically two to four. It is natural to ask whether this is a common feature of longest plane spanning trees, or an artifact of the specific approximation algorithms.\n          <\/jats:p>\n          <jats:p>\n            We provide three results to elucidate the interplay between the approximation guarantee and the unweighted diameter of the approximate trees. First, we describe a polynomial-time algorithm to construct a plane tree with diameter at most four and total edge length at least\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(0.546\\cdot\\mathrm{OPT}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            . This constitutes a substantial improvement over the state of the art. Second, we show that a longest plane tree among those with diameter at most three can be found in polynomial time. Third, for any candidate diameter\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(d\\geq 3\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            , we provide upper bounds on the approximation factor that can be achieved by a longest plane tree with diameter at most\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( d \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            (compared to a longest plane tree without constraints).\n          <\/jats:p>","DOI":"10.1145\/3765740","type":"journal-article","created":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T08:56:51Z","timestamp":1756976211000},"page":"1-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Long Plane Trees"],"prefix":"10.1145","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3183-4126","authenticated-orcid":false,"given":"Sergio","family":"Cabello","sequence":"first","affiliation":[{"name":"Faculty of Mathematics and Physics, University of Ljubljana, Ljubljana, Slovenia and Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5307-7106","authenticated-orcid":false,"given":"Michael","family":"Hoffmann","sequence":"additional","affiliation":[{"name":"ETH Z\u00fcrich, Z\u00fcrich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9884-3297","authenticated-orcid":false,"given":"Katharina","family":"Klost","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Informatik, Freie Universit\u00e4t Berlin, Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1948-5840","authenticated-orcid":false,"given":"Wolfgang","family":"Mulzer","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Informatik, Freie Universit\u00e4t Berlin, Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1097-9684","authenticated-orcid":false,"given":"Josef","family":"Tkadlec","sequence":"additional","affiliation":[{"name":"Computer Science Institute, Charles University, Praha, Czech Republic"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,10,7]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.3233\/FI-1995-2245"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12200-2_40"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290180"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1103-4"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/876638.876640"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.50"},{"key":"e_1_3_3_8_2","unstructured":"Ahmad Biniaz. 2020. Improved approximation ratios for two Euclidean maximum spanning tree problems. arXiv:2010.03870. Retrieved from https:\/\/arxiv.org\/abs\/2010.03870"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0482-x"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185434"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185434"},{"key":"e_1_3_3_12_2","article-title":"A better approximation for longest noncrossing spanning trees","author":"Cabello Sergio","year":"2020","unstructured":"Sergio Cabello, Aruni Choudhary, Michael Hoffmann, Katharina Klost, Meghana M. Reddy, Wolfgang Mulzer, Felix Schr\u00f6der, and Josef Tkadlec. 2020. A better approximation for longest noncrossing spanning trees. In Proceedings of the 36th European Workshop on Computational Geometry (EuroCG \u201920).","journal-title":"In Proceedings of the 36th European Workshop on Computational Geometry (EuroCG \u201920)"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-004-1117-3"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27798-9_8"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(84)80040-6"},{"key":"e_1_3_3_16_2","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","year":"2009","unstructured":"Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms (3rd ed.). MIT Press. Retrieved from http:\/\/mitpress.mit.edu\/books\/introduction-algorithms","edition":"3"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-010-9277-9"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0016-8"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/b978-044482537-7\/50010-3"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/1542362.1542399"},{"key":"e_1_3_3_22_2","volume-title":"New Results in Planar Triangulations","author":"Gilbert Peter D.","year":"1979","unstructured":"Peter D. Gilbert. 1979. New Results in Planar Triangulations. Technical Report R\u2013850. University of Illinois Coordinated Science Lab."},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1090\/surv\/173"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70044-X"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02573972"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796309764"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1201\/9781420035315.ch27"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1201\/9781315119601"},{"key":"e_1_3_3_29_2","volume-title":"Minimum Dilation Triangulations for the Regular  \\( n \\) -Gon","author":"Mulzer Wolfgang","year":"2004","unstructured":"Wolfgang Mulzer. 2004. Minimum Dilation Triangulations for the Regular \\( n \\) -Gon. Master\u2019s thesis. Freie Universit\u00e4t Berlin, Germany."},{"key":"e_1_3_3_30_2","first-page":"78:1","volume-title":"Proceedings of the 36th European Workshop on Computational Geometry (EWCG \u201920)","author":"Mulzer Wolfgang","year":"2020","unstructured":"Wolfgang Mulzer and Johannes Obenaus. 2020. The tree stabbing number is not monotone. In Proceedings of the 36th European Workshop on Computational Geometry (EWCG \u201920), 78:1\u201378:8."},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/1346330.1346336"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546884"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(77)90012-3"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(84)90029-4"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516517"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-55488-2_30"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3765740","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T15:06:16Z","timestamp":1759849576000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3765740"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,7]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,1,31]]}},"alternative-id":["10.1145\/3765740"],"URL":"https:\/\/doi.org\/10.1145\/3765740","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2025,10,7]]},"assertion":[{"value":"2024-04-30","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-07-31","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-10-07","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}