Exact Distance Oracles for Planar Graphs

Shay Mozes and Christian Sommer
SODA 2012 - 23rd ACM-SIAM Symposium on Discrete Algorithms (pp. 209-222)

We present exact distance oracles (data structures that answer node-to-node distance queries) in planar graphs. (running times up to poly-logarithmic factors)

For any directed planar graph on \(n\) nodes, given any space allocation \( S \in [n\lg\lg n,n^2]\), we construct in \(\widetilde{O}(S)\) time a data structure of size \(O(S)\) that answers queries in \(\widetilde{O}(n/\sqrt S)\) time. This was known only for \(S = n\) or \(S \gt n^{4/3}\).

For planar graphs with tree-width \(w = o(\sqrt n)\), we obtain an almost linear-space distance oracle with query time \(\widetilde{O}(w)\). Building on this, we provide an oracle with query time proportional to the distance between the query nodes. Comparable query performance had been observed experimentally but could not be explained theoretically.

@inproceedings{MS12,
 author    = {Shay Mozes and Christian Sommer},
 title     = {Exact Distance Oracles for Planar Graphs},
 year      = {2012},
 booktitle = {23rd ACM-SIAM Symposium on Discrete Algorithms (SODA)},
 pages     = {209--222},
 url       = {http://dx.doi.org/10.1137/1.9781611973099.19},
 doi       = {10.1137/1.9781611973099.19},
}

Official version
Local version (299.6 KB)
arXiv

News (Feb 2017): Cohen-Addad, Dahlgaard, and Wulff-Nilsen discovered a new and significantly improved distance oracle, based on a recent breakthrough result by Cabello. Their oracle uses \(O(n^{5/3})\) space and answers exact distance queries in logarithmic time.

For more information on our paper, see also my Video Lecture on Exact Distance Oracles at MIT, 6.889 L.12, discussing background, an efficient implementation of Dijkstra's algorithm (FR-Dijkstra, due to Fakcharoenphol and Rao), dense distance graphs, the Monge property, and more.

Podcast with Shay Mozes talking about our work


HomePublications → Exact Distance Oracles for Planar Graphs