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 Gawrychowski, Mozes, Weimann, and Wulff-Nilsen (Aug 2017) and Cohen-Addad, Dahlgaard, and Wulff-Nilsen (Feb 2017, accepted to FOCS) discovered a new and significantly improved distance oracles based on a recent breakthrough result by Cabello (SODA 2017).

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

Home → Publications → Exact Distance Oracles for Planar Graphs