Planar Reachability Under Single Vertex or Edge Failures
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.
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.
Research Areas
