Compact Oracles for Reachability and Approximate Distances in Planar Digraphs

摘要

It is shown that a planar digraph can be preprocessed in near-linear time, producing a near-linear space oracle that can answer reachability queries in constant time. The oracle can be distributed as an O(log n) space label for each vertex and then we can determine if one vertex can reach another considering their two labels only. The approach generalizes to give a near-linear space approximate distances oracle for a weighted planar digraph. With weights drawn from {0,..., N}, it approximates distances within a factor (1+ε) in O(log log(nN) + 1/ε) time. Our scheme can be extended to find and route along correspondingly short dipaths.