A Clique-Based Separator for Intersection Graphs of Geodesic Disks in $$\mathbb {R}^2$$
Boris S. Aronov, Mark de Berg, Leonidas Theocharous · Algorithmica · 2025
Abstract Let d be a (well-behaved) shortest-path metric defined on a path-connected subset of $$\mathbb {R}^2$$ and let $$\mathcal {D}=\{D_1,\ldots,D_n\}$$ be a set of geodesic disks with respect to the metric d. We prove that $$\mathcal {G}^{\times }(\mathcal {D})$$ , the intersection graph of the disks in $$\mathcal {D}$$ , has a clique-based separator consisting of $$O(n^{3/4+\varepsilon })$$ 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+\varepsilon })}$$ , 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+\varepsilon })$$ storage and can report the hop distance between any two nodes in $$\mathcal {G}^{\times }(\mathcal {D})$$ in $$O(n^{3/4+\varepsilon })$$ 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.