A Clique-Based Separator for Intersection Graphs of Geodesic Disks in R²

Let d be a (well-behaved) shortest-path metric defined on a path-connected subset of R² and let D = {D1, . . ., Dn} be a set of geodesic disks with respect to the metric d. We prove that G^×(D), the intersection graph of the disks in D, has a clique-based separator consisting of O(n³/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(ⁿ³/4+^ε), assuming the boundaries of the disks Di 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⁷/4+^ε) storage and can report the hop distance between any two nodes in G^×(D) in O(n³/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.