Abstract
Let d be a (well-behaved) shortest-path metric defined on a path-connected subset of ℝ² and let 𝒟 = {D_1,…,D_n} be a set of geodesic disks with respect to the metric d. We prove that 𝒢^×(𝒟), the intersection graph of the disks in 𝒟, has a clique-based separator consisting of O(n^{3/4+ε}) cliques. This significantly extends the class of objects whose intersection graphs have small clique-based separators.
Our clique-based separator yields an algorithm for q-Coloring that runs in time 2^O(n^{3/4+ε}), assuming the boundaries of the disks D_i 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 O(n^{7/4+ε}) storage and can report the hop distance between any two nodes in 𝒢^×(𝒟) in O(n^{3/4+ε}) 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.
Our clique-based separator yields an algorithm for q-Coloring that runs in time 2^O(n^{3/4+ε}), assuming the boundaries of the disks D_i 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 O(n^{7/4+ε}) storage and can report the hop distance between any two nodes in 𝒢^×(𝒟) in O(n^{3/4+ε}) 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.
Original language | English |
---|---|
Title of host publication | 40th International Symposium on Computational Geometry (SoCG 2024) |
Editors | Wolfgang Mulzer, Jeff M. Phillips |
Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
Pages | 9:1-9:15 |
Number of pages | 15 |
ISBN (Electronic) | 978-3-95977-316-4 |
DOIs | |
Publication status | Published - 6 Jun 2024 |
Event | 40th International Symposium on Computational Geometry - Eugenides Foundation, Athens, Greece Duration: 11 Jun 2024 → 14 Jun 2024 Conference number: 40 https://socg24.athenarc.gr/socg.html |
Publication series
Name | Leibniz International Proceedings in Informatics (LIPIcs) |
---|---|
Volume | 293 |
ISSN (Electronic) | 1868-8969 |
Conference
Conference | 40th International Symposium on Computational Geometry |
---|---|
Abbreviated title | SoCG 2024 |
Country/Territory | Greece |
City | Athens |
Period | 11/06/24 → 14/06/24 |
Internet address |
Funding
Boris Aronov: Work has been supported by NSF grant CCF 20-08551. Mark de Berg: MdB is supported by the Dutch Research Council (NWO) through Gravitation-grant NETWORKS-024.002.003.
Funders | Funder number |
---|---|
Nederlandse Organisatie voor Wetenschappelijk Onderzoek | |
National Science Foundation | CCF 20-08551 |
Keywords
- Computational geometry
- intersection graphs
- separator theorems