{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T00:20:21Z","timestamp":1759796421750,"version":"build-2065373602"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T00:00:00Z","timestamp":1756425600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T00:00:00Z","timestamp":1756425600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF 20-08551"],"award-info":[{"award-number":["CCF 20-08551"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["NETWORKS-024.002.003","NETWORKS-024.002.003"],"award-info":[{"award-number":["NETWORKS-024.002.003","NETWORKS-024.002.003"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2025,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Let <jats:italic>d<\/jats:italic> be a (well-behaved) shortest-path metric defined on a path-connected subset of <jats:inline-formula>\n              <jats:tex-math>$$\\mathbb {R}^2$$<\/jats:tex-math>\n            <\/jats:inline-formula> and let <jats:inline-formula>\n              <jats:tex-math>$$\\mathcal {D}=\\{D_1,\\ldots,D_n\\}$$<\/jats:tex-math>\n            <\/jats:inline-formula> be a set of geodesic disks with respect to the metric\u00a0<jats:italic>d<\/jats:italic>. We prove that <jats:inline-formula>\n              <jats:tex-math>$$\\mathcal {G}^{\\times }(\\mathcal {D})$$<\/jats:tex-math>\n            <\/jats:inline-formula>, the intersection graph of the disks in <jats:inline-formula>\n              <jats:tex-math>$$\\mathcal {D}$$<\/jats:tex-math>\n            <\/jats:inline-formula>, has a clique-based separator consisting of <jats:inline-formula>\n              <jats:tex-math>$$O(n^{3\/4+\\varepsilon })$$<\/jats:tex-math>\n            <\/jats:inline-formula> cliques. This significantly extends the class of objects whose intersection graphs have small clique-based separators. Our clique-based separator yields an algorithm for <jats:italic>q<\/jats:italic>-<jats:sc>Coloring<\/jats:sc> that runs in time <jats:inline-formula>\n              <jats:tex-math>$$2^{O(n^{3\/4+\\varepsilon })}$$<\/jats:tex-math>\n            <\/jats:inline-formula>, assuming the boundaries of the disks <jats:inline-formula>\n              <jats:tex-math>$$D_i$$<\/jats:tex-math>\n            <\/jats:inline-formula> can be computed in polynomial time. We also use our clique-based separator to obtain a simple, efficient, and almost exact distance oracle for intersection graphs of geodesic disks. Our distance oracle uses <jats:inline-formula>\n              <jats:tex-math>$$O(n^{7\/4+\\varepsilon })$$<\/jats:tex-math>\n            <\/jats:inline-formula> storage and can report the hop distance between any two nodes in <jats:inline-formula>\n              <jats:tex-math>$$\\mathcal {G}^{\\times }(\\mathcal {D})$$<\/jats:tex-math>\n            <\/jats:inline-formula> in <jats:inline-formula>\n              <jats:tex-math>$$O(n^{3\/4+\\varepsilon })$$<\/jats:tex-math>\n            <\/jats:inline-formula> time, up to an additive error of one. So far, distance oracles with an additive error of one that use subquadratic storage and sublinear query time were not known for such general graph classes.<\/jats:p>","DOI":"10.1007\/s00453-025-01337-5","type":"journal-article","created":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T04:14:46Z","timestamp":1756440886000},"page":"1997-2017","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Clique-Based Separator for Intersection Graphs of Geodesic Disks in $$\\mathbb {R}^2$$"],"prefix":"10.1007","volume":"87","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3110-4702","authenticated-orcid":false,"given":"Boris","family":"Aronov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5770-3784","authenticated-orcid":false,"given":"Mark","family":"de Berg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1707-6787","authenticated-orcid":false,"given":"Leonidas","family":"Theocharous","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,8,29]]},"reference":[{"key":"1337_CR1","doi-asserted-by":"publisher","unstructured":"Abraham, I., Gavoille, C.: On approximate distance labels and routing schemes with affine stretch. In: Proceedings 25th International Symposium on Distributed Computing (DISC 2011), volume 6950 of Lecture Notes in Computer Science (ARCoSS), pp. 404\u2013415 (2011). https:\/\/doi.org\/10.1007\/978-3-642-24100-0_39","DOI":"10.1007\/978-3-642-24100-0_39"},{"key":"1337_CR2","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Chv\u00e1tal, V., Newborn, M.M., Szemer\u00e9di, E.: Crossing-free subgraphs. In: Hammer, P.L., Rosa, A., Sabidussi, G., Turgeon, J. (eds.) Theory and Practice of Combinatorics, volume\u00a060 of North-Holland Mathematics Studies, pp. 9\u201312. North-Holland (1982)","DOI":"10.1016\/S0304-0208(08)73484-4"},{"key":"1337_CR3","doi-asserted-by":"publisher","unstructured":"Arikati, S.R., Chen, D.Z., Paul Chew, L., Das, G., Smid, M.H.M., Zaroliagis, C.D.: Planar spanners and approximate shortest path queries among obstacles in the plane. In: Proceedings\u00a04th Annual European Symposium on Algorithms (ESA 1996), volume 1136 of Lecture Notes in Computer Science, pp. 514\u2013528 (1996). https:\/\/doi.org\/10.1007\/3-540-61680-2_79","DOI":"10.1007\/3-540-61680-2_79"},{"key":"1337_CR4","doi-asserted-by":"publisher","unstructured":"Aronov, B., Berg, M.d., Theocharous, L.: A clique-based separator for intersection graphs of geodesic disks in [CDATA[{\\mathbb{R}}^2]]$${\\mathbb{R}}^2$$. In: Proceedings 40th International Symposium on Computational Geometry (SoCG 2024), LIPIcs, pp. 9:1\u20139:15 (2024). https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2024.9","DOI":"10.4230\/LIPIcs.SoCG.2024.9"},{"issue":"7","key":"1337_CR5","doi-asserted-by":"publisher","first-page":"3047","DOI":"10.1007\/s00453-019-00568-7","volume":"81","author":"\u00c9 Bonnet","year":"2019","unstructured":"Bonnet, \u00c9., Rzazewski, P.: Optimality program in segment and string graphs. Algorithmica 81(7), 3047\u20133073 (2019). https:\/\/doi.org\/10.1007\/s00453-019-00568-7","journal-title":"Algorithmica"},{"key":"1337_CR6","doi-asserted-by":"publisher","unstructured":"Chan, T.M., Skrepetos, D.: Approximate shortest paths and distance oracles in weighted unit-disk graphs. In: Proceedings\u00a034th International Symposium on Computational Geometry (SoCG 2018), vol.\u00a099, pp. 24 1\u201324 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2018.24","DOI":"10.4230\/LIPIcs.SoCG.2018.24"},{"key":"1337_CR7","doi-asserted-by":"publisher","unstructured":"Chang, H.-C., Gao, J., Le, H.: Computing diameter+2 in truly-subquadratic time for unit-disk graphs. In: Proceedings 40th International Symposium on Computational Geometry (SoCG 2024), volume 293 of LIPIcs, pp. 38:1\u201338:14 (2024). https:\/\/doi.org\/10.4230\/LIPICS.SOCG.2024.38","DOI":"10.4230\/LIPICS.SOCG.2024.38"},{"key":"1337_CR8","doi-asserted-by":"publisher","unstructured":"Charalampopoulos, P., Gawrychowski, P., Long, S.M., Y., Pettie, S., Weimann, O., Wulff-Nilsen, C,: Almost optimal exact distance oracles for planar graphs. J. ACM 70(2), 12:1-12:50 (2023). https:\/\/doi.org\/10.1145\/3580474","DOI":"10.1145\/3580474"},{"key":"1337_CR9","doi-asserted-by":"publisher","unstructured":"Chechik, S.: Approximate distance oracles with constant query time. In: Proceedings\u00a046th Symposium on Theory of Computing (STOC 2014), pp. 654\u2013663, (2014). https:\/\/doi.org\/10.1145\/2591796.2591801","DOI":"10.1145\/2591796.2591801"},{"key":"1337_CR10","doi-asserted-by":"publisher","unstructured":"de\u00a0Berg, M.: A note on reachability and distance oracles for transmission graphs. Comput. Geometry Topol. 2(1) 4:1\u20134:15 (2023). https:\/\/doi.org\/10.57717\/cgt.v2i1.25","DOI":"10.57717\/cgt.v2i1.25"},{"key":"1337_CR11","doi-asserted-by":"publisher","first-page":"1291","DOI":"10.1137\/20M1320870","volume":"49","author":"M de Berg","year":"2020","unstructured":"de Berg, M., Bodlaender, H.L., Kisfaludi-Bak, S., Marx, D., van der Zanden, T.C.: A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs. SIAM J. Comput. 49, 1291\u20131331 (2020). https:\/\/doi.org\/10.1137\/20M1320870","journal-title":"SIAM J. Comput."},{"issue":"6","key":"1337_CR12","doi-asserted-by":"publisher","first-page":"1652","DOI":"10.1007\/S00453-022-01041-8","volume":"85","author":"M de Berg","year":"2023","unstructured":"de Berg, M., Kisfaludi-Bak, S., Monemizadeh, M., Theocharous, L.: Clique-based separators for geometric intersection graphs. Algorithmica 85(6), 1652\u20131678 (2023). https:\/\/doi.org\/10.1007\/S00453-022-01041-8","journal-title":"Algorithmica"},{"issue":"3","key":"1337_CR13","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/s002360050082","volume":"34","author":"H Djidjev","year":"1997","unstructured":"Djidjev, H., Venkatesan, S.M.: Reduced constants for simple cycle graph separation. Acta Inform. 34(3), 231\u2013243 (1997). https:\/\/doi.org\/10.1007\/s002360050082","journal-title":"Acta Inform."},{"issue":"3","key":"1337_CR14","doi-asserted-by":"publisher","first-page":"1070","DOI":"10.1016\/j.aim.2008.06.002","volume":"219","author":"J Fox","year":"2008","unstructured":"Fox, J., Pach, J.: Separator theorems and Tur\u00e1n-type results for planar intersection graphs. Adv. Math. 219(3), 1070\u20131080 (2008). https:\/\/doi.org\/10.1016\/j.aim.2008.06.002","journal-title":"Adv. Math."},{"issue":"2","key":"1337_CR15","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1016\/j.jcss.2010.05.003","volume":"77","author":"B Fu","year":"2011","unstructured":"Fu, B.: Theory and application of width bounded geometric separators. J. Comput. Syst. Sci. 77(2), 379\u2013392 (2011). https:\/\/doi.org\/10.1016\/j.jcss.2010.05.003","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"1337_CR16","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1137\/S0097539703436357","volume":"35","author":"J Gao","year":"2005","unstructured":"Gao, J., Zhang, L.: Well-separated pair decomposition for the unit-disk graph metric and its applications. SIAM J. Comput. 35(1), 151\u2013169 (2005). https:\/\/doi.org\/10.1137\/S0097539703436357","journal-title":"SIAM J. Comput."},{"issue":"6","key":"1337_CR17","doi-asserted-by":"publisher","first-page":"1712","DOI":"10.1137\/16M1079336","volume":"46","author":"S Har-Peled","year":"2017","unstructured":"Har-Peled, S., Quanrud, K.: Approximation algorithms for polynomial-expansion and low-density graphs. SIAM J. Comput. 46(6), 1712\u20131744 (2017). https:\/\/doi.org\/10.1137\/16M1079336","journal-title":"SIAM J. Comput."},{"key":"1337_CR18","doi-asserted-by":"publisher","unstructured":"Kisfaludi-Bak, S., Okrasa, K., Rzazewski, P.: Computing list homomorphisms in geometric intersection graphs. In: Proceedings 48th Workshop on Graph-Theoretic Concepts in Computer Science (WG 2022), volume 13453 of Lecture Notes in Computer Science, pp. 313\u2013327 (2022). https:\/\/doi.org\/10.1007\/978-3-031-15914-5_23","DOI":"10.1007\/978-3-031-15914-5_23"},{"key":"1337_CR19","doi-asserted-by":"publisher","unstructured":"Le, H., Wulff-Nilsen, C.: Optimal approximate distance oracle for planar graphs. In: Proceedings\u00a062nd IEEE Annual Symposium on Foundations of Computer Science (FOCS 2021), pp. 363\u2013374. IEEE (2021). https:\/\/doi.org\/10.1109\/FOCS52979.2021.00044","DOI":"10.1109\/FOCS52979.2021.00044"},{"key":"1337_CR20","doi-asserted-by":"publisher","unstructured":"Lee, J.R.: Separators in region intersection graphs. In: Proceedings 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), volume\u00a067 of LIPIcs, pp. 1:1\u20131:8 (2017). https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2017.1","DOI":"10.4230\/LIPIcs.ITCS.2017.1"},{"key":"1337_CR21","unstructured":"Leighton, T.: Complexity Issues in VLSI. Foundations of Computing Series, MIT Press (2003)"},{"issue":"2","key":"1337_CR22","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"RJ Lipton","year":"1977","unstructured":"Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math. 36(2), 177\u2013189 (1977). https:\/\/doi.org\/10.1137\/0136016","journal-title":"SIAM J. Appl. Math."},{"issue":"1","key":"1337_CR23","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1145\/102782.102784","volume":"38","author":"JSB Mitchell","year":"1991","unstructured":"Mitchell, J.S.B., Papadimitriou, C.H.: The weighted region problem: Finding shortest paths through a weighted planar subdivision. J. ACM 38(1), 18\u201373 (1991). https:\/\/doi.org\/10.1145\/102782.102784","journal-title":"J. ACM"},{"key":"1337_CR24","doi-asserted-by":"publisher","unstructured":"Patrascu, M., Roditty, L.: Distance oracles beyond the Thorup-Zwick bound. In: Proceedings 51st Annual Symposium on Foundations of Computer Science (FOCS 2010), pp. 815\u2013823 (2010). https:\/\/doi.org\/10.1109\/FOCS.2010.83","DOI":"10.1109\/FOCS.2010.83"},{"issue":"4","key":"1337_CR25","doi-asserted-by":"publisher","first-page":"45:1","DOI":"10.1145\/2530531","volume":"46","author":"C Sommer","year":"2014","unstructured":"Sommer, C.: Shortest-path queries in static networks. ACM Comput. Surv. 46(4), 45:1-45:31 (2014). https:\/\/doi.org\/10.1145\/2530531","journal-title":"ACM Comput. Surv."},{"issue":"1","key":"1337_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1044731.1044732","volume":"52","author":"M Thorup","year":"2005","unstructured":"Thorup, M., Zwick, U.: Approximate distance oracles. J. ACM 52(1), 1\u201324 (2005). https:\/\/doi.org\/10.1145\/1044731.1044732","journal-title":"J. ACM"},{"key":"1337_CR27","unstructured":"Thurston, W.: The Geometry and Topology of 3-Manifolds. Princeton Lecture Notes, 1978\u20131981"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01337-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-025-01337-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01337-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,6]],"date-time":"2025-10-06T08:08:05Z","timestamp":1759738085000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-025-01337-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,29]]},"references-count":27,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["1337"],"URL":"https:\/\/doi.org\/10.1007\/s00453-025-01337-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2025,8,29]]},"assertion":[{"value":"1 October 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 July 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 August 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":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}