Quantcast

Fast and Compact Exact Distance Oracle for Planar Graphs

Research paper by Vincent Cohen-Addad, Søren Dahlgaard, Christian Wulff-Nilsen

Indexed on: 10 Feb '17Published on: 10 Feb '17Published in: arXiv - Computer Science - Data Structures and Algorithms



Abstract

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/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 - \epsilon})$ for some constant $\epsilon > 0$) either required query time polynomial in $n$ or could only answer approximate distance queries.