Compact oracles for reachability and approximate distances in planar digraphs

Abstract

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.