Distance oracles are data structures that provide fast (possibly approximate) answers to shortest-path and distance queries in graphs. The tradeoff between the space requirements and the query time of distance oracles is of particular interest and th
e main focus of this paper. In FOCS01, Thorup introduced approximate distance oracles for planar graphs. He proved that, for any eps>0 and for any planar graph on n nodes, there exists a (1+eps)-approximate distance oracle using space O(n eps^{-1} log n) such that approximate distance queries can be answered in time O(1/eps). Ten years later, we give the first improvements on the space-querytime tradeoff for planar graphs. * We give the first oracle having a space-time product with subquadratic dependency on 1/eps. For space ~O(n log n) we obtain query time ~O(1/eps) (assuming polynomial edge weights). The space shows a doubly logarithmic dependency on 1/eps only. We believe that the dependency on eps may be almost optimal. * For the case of moderate edge weights (average bounded by polylog(n), which appears to be the case for many real-world road networks), we hit a sweet spot, improving upon Thorups oracle both in terms of eps and n. Our oracle uses space ~O(n log log n) and it has query time ~O(log log log n + 1/eps). (Asymptotic notation in this abstract hides low-degree polynomials in log(1/eps) and log*(n).)
A (1 + eps)-approximate distance oracle for a graph is a data structure that supports approximate point-to-point shortest-path-distance queries. The most relevant measures for a distance-oracle construction are: space, query time, and preprocessing t
ime. There are strong distance-oracle constructions known for planar graphs (Thorup, JACM04) and, subsequently, minor-excluded graphs (Abraham and Gavoille, PODC06). However, these require Omega(eps^{-1} n lg n) space for n-node graphs. We argue that a very low space requirement is essential. Since modern computer architectures involve hierarchical memory (caches, primary memory, secondary memory), a high memory requirement in effect may greatly increase the actual running time. Moreover, we would like data structures that can be deployed on small mobile devices, such as handhelds, which have relatively small primary memory. In this paper, for planar graphs, bounded-genus graphs, and minor-excluded graphs we give distance-oracle constructions that require only O(n) space. The big O hides only a fixed constant, independent of epsilon and independent of genus or size of an excluded minor. The preprocessing times for our distance oracle are also faster than those for the previously known constructions. For planar graphs, the preprocessing time is O(n lg^2 n). However, our constructions have slower query times. For planar graphs, the query time is O(eps^{-2} lg^2 n). For our linear-space results, we can in fact ensure, for any delta > 0, that the space required is only 1 + delta times the space required just to represent the graph itself.
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 fo
llowing: * Given a desired space allocation $Sin[nlglg n,n^2]$, we show how to construct in $tilde O(S)$ time a data structure of size $O(S)$ that answers distance queries in $tilde O(n/sqrt S)$ time per query. As a consequence, we obtain an improvement over the fastest algorithm for k-many distances in planar graphs whenever $kin[sqrt n,n)$. * We provide a linear-space exact distance oracle for planar graphs with query time $O(n^{1/2+eps})$ for any constant eps>0. This is the first such data structure with provable sublinear query time. * For edge lengths at least one, we provide an exact distance oracle of space $tilde O(n)$ such that for any pair of nodes at distance D the query time is $tilde O(min {D,sqrt n})$. Comparable query performance had been observed experimentally but has never been explained theoretically. Our data structures are based on the following new tool: given a non-self-crossing cycle C with $c = O(sqrt n)$ nodes, we can preprocess G in $tilde O(n)$ time to produce a data structure of size $O(n lglg c)$ that can answer the following queries in $tilde O(c)$ time: for a query node u, output the distance from u to all the nodes of C. This data structure builds on and extends a related data structure of Klein (SODA05), which reports distances to the boundary of a face, rather than a cycle. The best distance oracles for planar graphs until the current work are due to Cabello (SODA06), Djidjev (WG96), and Fakcharoenphol and Rao (FOCS01). For $sigmain(1,4/3)$ and space $S=n^sigma$, we essentially improve the query time from $n^2/S$ to $sqrt{n^2/S}$.
