2026-07-23T05:51:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19954 2024-06-06T06:21:13Z ddc:004 open_access

A Clique-Based Separator for Intersection Graphs of Geodesic Disks in ℝ² Aronov, Boris de Berg, Mark Theocharous, Leonidas Computational geometry intersection graphs separator theorems 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Boris Aronov and Mark de Berg and Leonidas Theocharous 2024 Is Part Of LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2024.9 urn:nbn:de:0030-drops-199540 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.9 eng https://creativecommons.org/licenses/by/4.0/legalcode