Jump to Content

Planar Reachability Under Single Vertex or Edge Failures

Adam Karczmarz
Giuseppe F. Italiano
Nikos Parotsidis
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.