Object location using path separators

We propose a general approach to solve several object location problems in a large family of weighted graphs, namely in k-path separable graphs. Our main result is a separator theorem for graphs excluding a fixed minor that separates a graph using k-paths. Our proof uses the deep structure theorem of Robertson and Seymour. Given any k-path separable graph, we construct in polynomial time (1) a small-worldization with an average poly-logarithmic number of hops; (2) an (1 + ε)-approximate distance labeling scheme with O(log n) space labels; (3) a stretch-(1+ε) compact routing scheme with tables of poly-logarithmic space; (4) an (1+ε)-approximate distance oracle with O(nlog n) space and O(log n) query time. Such results apply, for instance, to planar graphs, bounded genus graphs, or bounded treewidth graphs. Actually our technique generalizes to bounded-dimension isometric separators, and similar results apply to much wider classes of weighted graphs