Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus, and Minor-Free Graphs

Ken-ichi Kawarabayashi, Philip N. Klein, and Christian Sommer
ICALP 2011 - 38th International Colloquium on Automata, Languages and Programming, Track A: Algorithms, Complexity and Games (pp. 135-146)

A \((1+\epsilon)\)-approximate distance oracle for a graph is a data structure that supports approximate point-to-point shortest-path-distance queries. The relevant measures for a distance-oracle construction are: space, query time, and preprocessing time.

There are strong distance-oracle constructions known for planar graphs (Thorup, JACM 04) and, subsequently, minor-excluded graphs (Abraham and Gavoille, PODC 06). However, these require \(\Omega(\epsilon^{-1}n\log 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. Our constructions have proportionately higher query times. For planar graphs, the query time is \(O(\epsilon^{-2}\log^2n)\). The preprocessing times for our distance oracle are also better than those for the previously known constructions. For planar graphs, the preprocessing time is \(O(n\log^2n)\).

For bounded-genus graphs, there was previously no distance-oracle construction known other than the one implied by the minor-excluded construction, for which the constant is enormous and the preprocessing time is a high-degree polynomial. In our result, the query time is \(O(\epsilon^{-2}(g+\log n)^2)\) and the preprocessing time is \(O(n(\log n)(g^3 + \log n))\).

For all these linear-space results, we can in fact ensure, for any \(\delta \gt 0\), that the space required is only \(1+\delta\) times the space required just to represent the graph itself.

@inproceedings{KKS11,
 author    = {{Ken-ichi} Kawarabayashi 
              and Philip N. Klein 
              and Christian Sommer},
 title     = {Linear-Space Approximate Distance Oracles 
              for Planar, Bounded-Genus and Minor-Free Graphs},
 booktitle = {38th International Colloquium on 
              Automata, Languages and Programming (ICALP)},
 year      = {2011},
 pages     = {135--146},
 url       = {http://dx.doi.org/10.1007/978-3-642-22006-7_12},
 doi       = {10.1007/978-3-642-22006-7_12},
}

Official version
Local version (255.7 KB)
arXiv
Slides (2.5 MB)

Home → Publications → Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus, and Minor-Free Graphs