Exact Distance Oracles for Planar Graphs
Shay Mozes, Christian Sommer · 2010
We present new and improved data structures that answer exact node-to-node distance queries in planar graphs. Such data structures are also known as distance oracles. For any directed planar graph on n nodes with non-negative lengths we obtain the following: 1 • Given a desired space allocation S ∈ [n lg lg n, n 2], we show how to construct in Õ(S) time a data structure of size O(S) that answers distance queries in Õ(n/√S) time per query. As a consequence, we obtain an improvement over the fastest algorithm for k–many distances in planar graphs whenever k ∈ [ √ n, n). • We provide a linear-space exact distance oracle for planar graphs with query time O(n 1/2+ɛ) for any constant ɛ> 0. This is the first such data structure with provable sublinear query time. • For edge lengths ≥ 1, we provide an exact distance oracle of space Õ(n) such that for any pair of nodes at distance ℓ the query time is Õ(min{ℓ, √ n}). Comparable query performance had been observed experimentally but could not be proven. Our data structures are based on the following new tool: given a non-self-crossing cycle C with c = O ( √ n) nodes, we can preprocess G in Õ(n) time to produce a data structure of size O(n lg lg c) that