Planar Reachability Under Single Vertex or Edge Failures

Adam Karczmarz
Giuseppe F. Italiano
SODA 2021 (to appear)
Google Scholar

Abstract

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 log^2 n/log log n) time, producing an O(n log n)-space data structure that can
answer in O(log n) time whether u can reach v in G if the vertex x (the edge f) is removed from
G, for any query vertices u, v and failed vertex x (failed edge f). To the best of our knowledge,
this is the first data structure for planar directed graphs with nearly-optimal preprocessing time
that is capable of answering all-pairs queries under any kind of failures in polylogarithmic time.

We also consider 2-reachability problems, where we are given a planar digraph G and we
wish to determine if there are two vertex-disjoint (edge-disjoint) paths from u to v, for query
vertices u, v. In this setting we provide a nearly-optimal 2-reachability oracle, which is the
existential variant of the reachability oracle under single failures, with the following bounds. We
can construct in O(n polylog n) time an O(n log^{3+o(1)} n)-space data structure that can check in
O(log^{2+o(1)} n) time for any query vertices u, v whether v is 2-reachable from u, or otherwise find
some separating vertex (edge) x lying on all paths from u to v in G.

To obtain our results, we follow the general recursive approach of Thorup for reachability in
planar graphs [J. ACM ’04] and we present new data structures which generalize dominator trees
and previous data structures for strong-connectivity under failures [Georgiadis et al., SODA ’17].
Our new data structures work also for general digraphs and may be of independent interest.