Fast and Compact Exact Distance Oracle for Planar Graphs
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 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">5/3</sup> )-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 …