{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:08:49Z","timestamp":1750219729650,"version":"3.41.0"},"reference-count":66,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,6,21]],"date-time":"2024-06-21T00:00:00Z","timestamp":1718928000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science Foundation","award":["CCF-2121952"],"award-info":[{"award-number":["CCF-2121952"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2024,7,31]]},"abstract":"\n The greedy spanner in a low-dimensional Euclidean space is a fundamental geometric construction that has been extensively studied over three decades, as it possesses the two most basic properties of a good spanner: constant maximum degree and constant lightness. Recently, Eppstein and Khodabandeh\u00a0[\n 28<\/jats:xref>\n ] showed that the greedy spanner in\n \n \\(\\mathbb {R}^2\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n admits a sublinear separator in a strong sense: Any subgraph of\n k<\/jats:italic>\n vertices of the greedy spanner in\n \n \\(\\mathbb {R}^2\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n has a separator of size\n \n \\(O(\\sqrt {k})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . Their technique is inherently planar and is not extensible to higher dimensions. They left showing the existence of a small separator for the greedy spanner in\n \n \\(\\mathbb {R}^d\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n for any constant\n d<\/jats:italic>\n \u2265 3 as an open problem.\n <\/jats:p>\n \n In this article, we resolve the problem of Eppstein and Khodabandeh\u00a0[\n 28<\/jats:xref>\n ] by showing that any subgraph of\n k<\/jats:italic>\n vertices of the greedy spanner in\n \n \\(\\mathbb {R}^d\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n has a separator of size\n \n \\(O(k^{1-1\/d})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . We introduce a new technique that gives a simple criterion for any geometric graph to have a sublinear separator that we dub\n \u03c4-lanky<\/jats:italic>\n : A geometric graph is \u03c4-lanky if any ball of radius\n r<\/jats:italic>\n cuts at most \u03c4 edges of length at least\n r<\/jats:italic>\n in the graph. We show that any \u03c4-lanky geometric graph of\n n<\/jats:italic>\n vertices in\n \n \\(\\mathbb {R}^d\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n has a separator of size\n \n \\(O(\\tau n^{1-1\/d})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . We then derive our main result by showing that the greedy spanner is\n O<\/jats:italic>\n (1)-lanky. We indeed obtain a more general result that applies to unit ball graphs and point sets of low fractal dimensions in\n \n \\(\\mathbb {R}^d\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n .\n <\/jats:p>\n \n Our technique naturally extends to doubling metrics. We use the \u03c4-lanky criterion to show that there exists a (1+\u03b5)-spanner for doubling metrics of dimension\n d<\/jats:italic>\n with a constant maximum degree and a separator of size\n \n \\(O(n^{1-\\frac{1}{d}})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n ; this result resolves an open problem posed by Abam and Har-Peled\u00a0[\n 1<\/jats:xref>\n ] a decade ago. We then introduce another simple criterion for a graph in doubling metrics of dimension\n d<\/jats:italic>\n to have a sublinear separator. We use the new criterion to show that the greedy spanner of an\n n<\/jats:italic>\n -point metric space of doubling dimension\n d<\/jats:italic>\n has a separator of size\n \n \\(O((n^{1-\\frac{1}{d}}) + \\log \\Delta)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n where \u0394 is the spread of the metric; the factor log (\u0394) is tightly connected to the fact that, unlike its Euclidean counterpart, the greedy spanner in doubling metrics has\n unbounded maximum degree<\/jats:italic>\n . Finally, we discuss algorithmic implications of our results.\n <\/jats:p>","DOI":"10.1145\/3590771","type":"journal-article","created":{"date-parts":[[2023,4,3]],"date-time":"2023-04-03T12:20:45Z","timestamp":1680524445000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Greedy Spanners in Euclidean Spaces Admit Sublinear Separators"],"prefix":"10.1145","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8223-9944","authenticated-orcid":false,"given":"Hung","family":"Le","sequence":"first","affiliation":[{"name":"University of Massachusetts Amherst, Amherst, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7350-331X","authenticated-orcid":false,"given":"Cuong","family":"Than","sequence":"additional","affiliation":[{"name":"University of Massachusetts Amherst, Amherst, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,6,21]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_3_3_2_2","DOI":"10.1145\/1810959.1810993"},{"doi-asserted-by":"publisher","key":"e_1_3_3_3_2","DOI":"10.1007\/BF02189308"},{"doi-asserted-by":"publisher","key":"e_1_3_3_4_2","DOI":"10.1145\/225058.225191"},{"doi-asserted-by":"publisher","key":"e_1_3_3_5_2","DOI":"10.1145\/323596.323621"},{"volume-title":"Technical Report CS92-22, Weizmann Institute","author":"Awerbuch B.","unstructured":"B. Awerbuch, A. Baratz, and D. Peleg. October, 1992. Efficient broadcast and light-weight spanners. Technical Report CS92-22, Weizmann Institute.","key":"e_1_3_3_6_2"},{"doi-asserted-by":"publisher","key":"e_1_3_3_7_2","DOI":"10.1145\/174644.174650"},{"doi-asserted-by":"publisher","key":"e_1_3_3_8_2","DOI":"10.1023\/a:1016747704458"},{"doi-asserted-by":"publisher","key":"e_1_3_3_9_2","DOI":"10.1109\/PIMRC.2004.1373851"},{"doi-asserted-by":"publisher","key":"e_1_3_3_10_2","DOI":"10.1109\/FOCS.2017.76"},{"doi-asserted-by":"publisher","key":"e_1_3_3_11_2","DOI":"10.1137\/1.9781611975482.145"},{"doi-asserted-by":"publisher","key":"e_1_3_3_12_2","DOI":"10.1016\/j.dam.2015.03.004"},{"issue":"4","key":"e_1_3_3_13_2","first-page":"55:1\u201355:22","article-title":"On hierarchical routing in doubling metrics","volume":"12","author":"Chan T.-H. H.","year":"2016","unstructured":"T.-H. H. Chan, A. Gupta, B. M. Maggs, and S. Zhou. 2016. On hierarchical routing in doubling metrics. ACM Trans. Algor. 12, 4 (2016), 55:1\u201355:22.","journal-title":"ACM Trans. Algor."},{"key":"e_1_3_3_14_2","volume-title":"16th ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Chan T.-H. Hubert","year":"2005","unstructured":"T.-H. Hubert Chan, Anupam Gupta, Bruce M. Maggs, and Shuheng Zhou. 2005. On hierarchical routing in doubling metrics. In 16th ACM-SIAM Symposium on Discrete Algorithms (SODA)."},{"doi-asserted-by":"publisher","key":"e_1_3_3_15_2","DOI":"10.1145\/142675.142717"},{"doi-asserted-by":"publisher","key":"e_1_3_3_16_2","DOI":"10.1145\/10515.10534"},{"doi-asserted-by":"publisher","key":"e_1_3_3_17_2","DOI":"10.1109\/FOCS46700.2020.00061"},{"doi-asserted-by":"publisher","key":"e_1_3_3_18_2","DOI":"10.1109\/ICCD.1991.139874"},{"doi-asserted-by":"publisher","key":"e_1_3_3_19_2","DOI":"10.1109\/43.137519"},{"doi-asserted-by":"publisher","key":"e_1_3_3_20_2","DOI":"10.1145\/160985.160998"},{"doi-asserted-by":"publisher","key":"e_1_3_3_21_2","DOI":"10.1145\/1077464.1077468"},{"key":"e_1_3_3_22_2","first-page":"590","volume-title":"16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201905)","author":"Demaine E. D.","year":"2005","unstructured":"E. D. Demaine and M. Hajiaghayi. 2005. Bidimensionality: New connections between FPT algorithms and PTASs. In 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201905). 590\u2013601."},{"doi-asserted-by":"publisher","key":"e_1_3_3_23_2","DOI":"10.1109\/SFCS.2005.14"},{"doi-asserted-by":"publisher","key":"e_1_3_3_24_2","DOI":"10.1137\/20m1311156"},{"doi-asserted-by":"publisher","key":"e_1_3_3_25_2","DOI":"10.5555\/3174304.3175415"},{"doi-asserted-by":"publisher","key":"e_1_3_3_26_2","DOI":"10.1137\/15M1017569"},{"doi-asserted-by":"publisher","key":"e_1_3_3_27_2","DOI":"10.1145\/2819008"},{"doi-asserted-by":"publisher","key":"e_1_3_3_28_2","DOI":"10.1007\/s004530010020"},{"key":"e_1_3_3_29_2","volume-title":"37th International Symposium on Computational Geometry (SoCG\u20192021)","author":"Eppstein D.","year":"2021","unstructured":"D. Eppstein and H. Khodabandeh. 2021. On the edge crossings of the greedy spanner. In 37th International Symposium on Computational Geometry (SoCG\u20192021)."},{"doi-asserted-by":"publisher","key":"e_1_3_3_30_2","DOI":"10.5555\/2383356.2383357"},{"key":"e_1_3_3_31_2","first-page":"29","article-title":"Extremal problems in graph theory","author":"Erd\u0151s P.","year":"1964","unstructured":"P. Erd\u0151s. 1964. Extremal problems in graph theory. Theory of Graphs and Its Applications (Proc. Sympos. Smolenice) (1964), 29\u201336.","journal-title":"Theory of Graphs and Its Applications (Proc. Sympos. Smolenice)"},{"doi-asserted-by":"publisher","key":"e_1_3_3_32_2","DOI":"10.1145\/2933057.2933114"},{"doi-asserted-by":"publisher","key":"e_1_3_3_33_2","DOI":"10.1109\/focs.2016.62"},{"issue":"1","key":"e_1_3_3_34_2","first-page":"31","article-title":"Spanners for geometric intersection graphs with applications","volume":"3","author":"F\u00fcrer M.","year":"2012","unstructured":"M. F\u00fcrer and S. P. Kasiviswanathan. 2012. Spanners for geometric intersection graphs with applications. J. Computat. Geom. 3, 1 (2012), 31\u201364.","journal-title":"J. Computat. Geom."},{"doi-asserted-by":"publisher","key":"e_1_3_3_35_2","DOI":"10.1137\/s0097539703436357"},{"doi-asserted-by":"publisher","key":"e_1_3_3_36_2","DOI":"10.1109\/FOCS.2015.52"},{"doi-asserted-by":"publisher","key":"e_1_3_3_37_2","DOI":"10.1109\/TIT.2017.2713820"},{"doi-asserted-by":"publisher","key":"e_1_3_3_38_2","DOI":"10.1137\/20m1311156"},{"key":"e_1_3_3_39_2","article-title":"A simple proof of the existence of a planar separator","author":"Har-Peled S.","year":"2011","unstructured":"S. Har-Peled. 2011. A simple proof of the existence of a planar separator. arXiv preprint arXiv:1105.0103 (2011). https:\/\/arxiv.org\/abs\/1105.0103.","journal-title":"arXiv preprint arXiv:1105.0103"},{"doi-asserted-by":"publisher","key":"e_1_3_3_40_2","DOI":"10.1137\/s0097539704446281"},{"doi-asserted-by":"publisher","key":"e_1_3_3_41_2","DOI":"10.1137\/16m1079336"},{"doi-asserted-by":"publisher","key":"e_1_3_3_42_2","DOI":"10.1006\/jcss.1997.1493"},{"key":"e_1_3_3_43_2","volume-title":"On the Maximum Weighted Independent Set Problem with Applications in Wireless Sensor Networks","author":"Huang F.","year":"2013","unstructured":"F. Huang. 2013. On the Maximum Weighted Independent Set Problem with Applications in Wireless Sensor Networks. Boston University."},{"doi-asserted-by":"publisher","key":"e_1_3_3_44_2","DOI":"10.1109\/SFCS.2005.7"},{"doi-asserted-by":"publisher","key":"e_1_3_3_45_2","DOI":"10.1145\/1132516.1132620"},{"doi-asserted-by":"publisher","key":"e_1_3_3_46_2","DOI":"10.1109\/FOCS.2019.00069"},{"doi-asserted-by":"publisher","key":"e_1_3_3_47_2","DOI":"10.1109\/TC.2003.1204831"},{"doi-asserted-by":"publisher","key":"e_1_3_3_48_2","DOI":"10.1137\/0209046"},{"doi-asserted-by":"publisher","key":"e_1_3_3_49_2","DOI":"10.1007\/978-3-642-03417-6_4"},{"doi-asserted-by":"publisher","key":"e_1_3_3_50_2","DOI":"10.4230\/LIPIcs.ESA.2017.59"},{"doi-asserted-by":"publisher","key":"e_1_3_3_51_2","DOI":"10.1145\/256292.256294"},{"doi-asserted-by":"publisher","key":"e_1_3_3_52_2","DOI":"10.1017\/CBO9780511546884"},{"doi-asserted-by":"publisher","key":"e_1_3_3_53_2","DOI":"10.1137\/1.9780898719772"},{"doi-asserted-by":"publisher","key":"e_1_3_3_54_2","DOI":"10.1002\/jgt.3190130114"},{"doi-asserted-by":"publisher","key":"e_1_3_3_55_2","DOI":"10.1109\/access.2018.2819083"},{"doi-asserted-by":"publisher","key":"e_1_3_3_56_2","DOI":"10.1145\/276698.276868"},{"doi-asserted-by":"publisher","key":"e_1_3_3_57_2","DOI":"10.1142\/9789812702456_0005"},{"doi-asserted-by":"publisher","key":"e_1_3_3_58_2","DOI":"10.1137\/S1052623497321432"},{"doi-asserted-by":"publisher","key":"e_1_3_3_59_2","DOI":"10.1109\/TNET.2010.2053381"},{"doi-asserted-by":"publisher","key":"e_1_3_3_60_2","DOI":"10.4230\/LIPIcs.SoCG.2017.58"},{"doi-asserted-by":"publisher","key":"e_1_3_3_61_2","DOI":"10.1109\/infocom.2014.6848130"},{"doi-asserted-by":"publisher","key":"e_1_3_3_62_2","DOI":"10.1007\/978-3-642-03456-5_19"},{"doi-asserted-by":"publisher","key":"e_1_3_3_63_2","DOI":"10.1109\/sfcs.1998.743449"},{"doi-asserted-by":"publisher","key":"e_1_3_3_64_2","DOI":"10.1145\/1022630.1022640"},{"doi-asserted-by":"publisher","key":"e_1_3_3_65_2","DOI":"10.4108\/ICST.WICON2008.4862"},{"doi-asserted-by":"publisher","key":"e_1_3_3_66_2","DOI":"10.1016\/j.comcom.2012.10.005"},{"doi-asserted-by":"publisher","key":"e_1_3_3_67_2","DOI":"10.1016\/j.tcs.2008.10.032"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3590771","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3590771","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:36:26Z","timestamp":1750178186000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3590771"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,21]]},"references-count":66,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,7,31]]}},"alternative-id":["10.1145\/3590771"],"URL":"https:\/\/doi.org\/10.1145\/3590771","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2024,6,21]]},"assertion":[{"value":"2022-05-02","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-03-09","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-06-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}