Fast and Compact Exact Distance Oracle for Planar Graphs

For a given a graph, a distance oracle is a data structure that answers distance queries between pairs of vertices. We introduce an $O(n^{5\mathrm{/}3})$-space distance oracle which answers exact distance queries in $O(\log n)$ time for $n$-vertex planar edge-weighted digraphs. All previous distance oracles for planar graphs with truly subquadratic space i.e., space $O(n^{2-ϵ})$ for some constant $ϵ>0$) either required query time polynomial in $n$ or could only answer approximate distance queries. Furthermore, we show how to trade-off time and space: for any $S \ge n^{3/2}$,weshowhowtoobtainan$S$-space distance oracle that answers queries in time $O((n^{5\mathrm{/}2}\mathrm{/}{S}^{3\mathrm{/}2})\log n)$. This is a polynomial improvement over the previous planar distance oracles with $o(n^{1\mathrm{/}4})$ query time.