A Clique-Based Separator for Intersection Graphs of Geodesic Disks in [Formula: see text].

Let d be a (well-behaved) shortest-path metric defined on a path-connected subset of [Formula: see text] and let [Formula: see text] be a set of geodesic disks with respect to the metric d. We prove that [Formula: see text], the intersection graph of the disks in [Formula: see text], has a clique-based separator consisting of [Formula: see text] 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 [Formula: see text], assuming the boundaries of the disks [Formula: see text] 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 [Formula: see text] storage and can report the hop distance between any two nodes in [Formula: see text] in [Formula: see text] 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.