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 n<S<n2, we construct in O(S) time a data structure of size O(S) that answers queries in O(n/√S) time. This was known only for S=n or S>n4/3.

For planar graphs with tree-width w=o(√n), we obtain an almost linear-space distance oracle with query time 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.

See also: 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.


@inproceedings{MozesSommerSODA12,
   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},
}