Planar Reachability Under Single Vertex or Edge Failures
Planar Reachability Under Single Vertex or Edge Failures
In this paper we present an efficient reachability oracle under single-edge or single-vertex failures for planar directed graphs. Specifically, we show that a planar digraph G can be preprocessed in O(n log2 n/log log n) time, producing an O(n log n)-space data structure that can answer in O(log n) time …