# Planar Reachability Under Single Vertex or Edge Failures

Giuseppe F. Italiano Giuseppe F. Italiano is partially supported by MUR, the
Italian Ministry for University and Research, under PRIN Project AHeAD
(Efficient Algorithms for HArnessing Networked Data). LUISS University, Rome,
Italy  Adam Karczmarz Supported by ERC Consolidator Grant 772346 TUgbOAT, the
Polish National Science Centre 2018/29/N/ST6/00757 grant, and by the
Foundation for Polish Science (FNP) via the START programme. Institute of
Informatics, University of Warsaw, Poland  Nikos Parotsidis This work was
partially done while the author was employed at the University of Copenhagen
supported by the Grant Number 16582, Basic Algorithms Research Copenhagen
(BARC), from the VILLUM Foundation. Google Research

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 answers 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\operatorname{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.

##  1 Introduction

Computing reachability is perhaps one of the most fundamental problems in
directed graphs. Let $G=(V,E)$ be a directed graph with $n$ vertices and $m$
edges. The transitive closure (i.e., all-pairs reachability) problem consists
of computing whether there is a directed path from $u$ to $v$, for all pairs
of vertices $u,v\in V$. The single-source reachability variant asks for each
$v\in V$ whether there exists a path from $s$ to $v$, where $s\in V$ is fixed.
While single-source reachability can be solved in optimal $O(m)$ time, the
fastest algorithm for computing transitive closure runs in
$\widetilde{O}(\min(n^{\omega},nm))$ time, where $\omega<2.38$ is the matrix
multiplication exponent. Notice that for solving the all-pairs reachability
problem one needs $O(n^{2})$ space to store the information for all pairs of
vertices.

In the oracle variant of all-pairs reachability, we wish to preprocess the
input graph and build a data structure that can answer reachability queries
between any pair of vertices, while trying to minimize the query time, the
preprocessing time, as well as the size of the data structure. Henzinger et
al. [34] gave conditional lower bounds for ’’combinatorial‘‘111That is, not
relying on fast matrix multiplication algorithms, which are often considered
impractical. constructions for this problem. Specifically, they showed that
there is no all-pairs reachability oracle that simultaneously requires
$O(n^{3-\epsilon})$ time preprocessing and supports queries in
$O(n^{2-\epsilon})$ time (for all $m$), unless there is a truly
’’combinatorial‘‘ algorithm that can multiply two $n\times n$ boolean matrices
in $O(n^{3-\epsilon})$ time.

However, non-trivial reachability oracles are known for a few important graph
classes. Most notably, for planar digraphs, for which $m=O(n)$, the first
reachability oracle with near-linear preprocessing and polylogarithmic query
time was obtained by Thorup [54], whereas a decade later Holm et al. [35]
presented an asymptotically optimal oracle, with $O(n)$ space and
preprocessing time and constant query time. For graph classes admitting
balanced separators of size $s(n)$ (which include graphs with treewidth
$O(s(n))$, and minor-free graphs for $s(n)=O(\sqrt{n})$), an
$\widetilde{O}(n\cdot s(n))$-space reachability oracle with query time
$\widetilde{O}(s(n))$ exists222To obtain such an oracle it is enough to
precompute single-source reachability from/to all the $O(s(n))$ vertices of
the separator and recurse on the components of $G$ after removing the
separator..

Real-world networks undoubtedly experience link or node failures. This has
motivated the research community to develop graph algorithms and data
structures that can efficiently deal with failures. A notable example is the
notion of dominators in digraphs with respect to a source vertex $s$. We say
that a vertex $x$ dominates a vertex $v$ if all paths from $s$ to $v$ contain
$x$. The dominance relation from $s$ is transitive and can be represented via
a tree called the _dominator tree_ from $s$. The dominator tree from $s$
allows one to answer several reachability under failure queries, such as ’’are
there two edge- (or vertex-) disjoint paths from $s$ to $v$?” and ’’is there a
path from $s$ to $v$ avoiding a vertex $x$ (or an edge $e$)?”, in
asymptotically optimal time. The notion of dominators has been widely used in
domains like circuit testing [7], theoretical biology [5], memory profiling
[44], constraint programming [46], connectivity [27], just to state some. Due
to their numerous applications, dominators have been extensively studied for
over four decades [4, 37, 41, 51] and several linear-time algorithms for
computing dominator trees are known [6, 14, 15, 29]. While extremely useful,
dominator trees are restricted to answering queries only from a single source
$s$.

Oracles that answer queries in the presence of failures are often called _$f$
-sensitivity oracles_333We adopt the use of the term from [34]. We note that
other terms have also been used in the literature, such as “fault-tolerant”
oracles or oracles ”for failure prone graphs”., where $f$ refers to the upper
bound on the number of failures allowed. If not explicitly mentioned, in this
paper when we refer to sensitivity oracles we refer to $1$-sensitivity oracles
that allow failures of either one edge or one vertex. In what follows we
denote by $G-F$ the graph obtained from $G$ after deleting the set of vertices
or edges $F$. If $F$ is a single vertex or edge $x$, we write $G-x$.

In this paper, we study 1-sensitivity oracles for the all-pairs reachability
problem in planar digraphs. Specifically, we wish to preprocess a planar graph
efficiently and build a possibly small (in terms of space) data structure that
can efficiently answer queries of the form ’’is there a path from $u$ to $v$
avoiding $x$?”, for query vertices $u,v$ and vertex (or edge) $x$. Moreover,
we study _2-reachability problems_ , where, given a directed graph $G$, we
wish to determine if there are two vertex-disjoint (resp., edge-disjoint)
paths from $u$ to $v$, for query vertices $u,v$. In particular, we consider
_2-reachability oracles_ , which are the existential variant of 1-sensitivity
reachability oracles. Here, the desired data structure should, for an
arbitrary pair of query vertices $(u,v)$, efficiently find a vertex
$x\notin\\{u,v\\}$ (resp., an edge $e$) whose failure destroys all $u\to v$
paths in the graph, or declare there is none. Note that in the latter case,
vertex $v$ is 2-reachable from vertex $u$444The name 2-reachability comes from
the fact that, by Menger’s theorem, there exist two internally vertex-disjoint
$u\to v$ paths if and only if no single failing vertex can make $v$
unreachable from $u$.

Our data structures support the aforementioned queries answered with dominator
trees, but we allow a source $s$ to be a query parameter as well, as opposed
to a dominator tree which assumes a fixed source. We focus on planar graphs
not only because they are one of the most studied non-general classes of
graphs, but also because dominator trees have been used in the past for
solving problems on planar graphs (i.e., circuit testing [7]), and hence our
result could potentially motivate further similar applications as an efficient
tool that can answer all-pairs dominance queries.

Notice that a simple-minded solution to both 1-sensitivity reachability oracle
and 2-reachability oracle problems with $O(n^{2})$ space and preprocessing
time and $O(1)$ query time is to compute the dominator tree from each source
vertex $s$. In general directed graphs, the all-pairs version of a dominator
tree cannot be computed faster than matrix-multiplication or be stored in
subquadratic space [30], which can be prohibitive in applications that require
the processing of data of even moderate size. In this paper we show how to
achieve significantly better bounds for both these problems when the input
digraph is planar.

#### Related work.

There has been an extensive study of sensitivity oracles in directed graphs,
with the initial studies dating several decades back. Sensitivity oracles for
single-source reachability have been studied widely under the name _dominator
trees_ since the seventies (see e.g., [41]). Choudhary [20] considered the
problem of computing $2$-sensitivity oracles for single-source reachability.
In particular, she showed how to construct a data structure of size $O(n)$
that can answer in constant time reachability queries from a source $s$ to any
vertex $v$ in $G-\\{x,y\\}$, for query vertices $v,x,y$. While the
preprocessing time is not specified, a simple-minded initialization of her
data structure requires $O(mn^{2})$ time. Baswana et al. [8], considered the
version of this problem with multiple failures. Specifically, they presented
an $f$-sensitivity oracle, with size $O(2^{f}n)$ and preprocessing time
$O(mn)$, that can compute the set or reachable vertices from the source vertex
$s$ in $G-F$ in $O(2^{f}n)$ time, where $F$ is the set of failed vertices or
edges, with $|F|\leq f$.

King and Sagert [39] were the first to study 1-sensitivity oracles for all-
pairs reachability under single edge failures. In particular, they gave an
algorithm that can answer queries in constant time in directed acyclic graphs
(DAGs), after $O(n^{3})$ time preprocessing. For general directed graphs
Georgiadis et al. [30] showed a near-optimal 1-sensitivity oracle for all-
pairs reachability, with $O(n^{2})$ space and $O(\min\\{mn,n^{\omega}\log
n\\})$ preprocessing time, that can answer in constant time queries of the
form ’’is there a path from $u$ to $v$ in $G-x$”, for query vertices $u,v$ and
failing vertex or edge $x$. Their approach first produces dominator trees from
all sources, which are then used to answer the queries. Sensitivity oracles
for reachability problems admit a trivial lower bound: they cannot be built
faster than the time it takes to compute the corresponding (single-source or
all-pairs) reachability problem in the static case (i.e., without failures).
Very recently, van den Brand and Saranurak [55] presented an $f$-sensitivity
oracle for all-pairs reachability with $O(n^{2}\log n)$ size and
$O(f^{\omega})$ query time, and $O(n^{\omega})$ time preprocessing. Their
$f$-sensitivity oracle is nearly optimal for $f\in O(1)$ and is obtained by
adopting an improved $f$-sensitivity oracle for the All-Pairs Shortest Paths
problem. Therefore, the problem of constructing an $f$-sensitivity all-pairs
reachability oracle in general digraphs is well understood for small values of
$f$.

As already mentioned, the $2$-reachability problem asks to build a data
structure that can efficiently report for a pair of query vertices $(u,v)$ a
single vertex (resp., edge) that appears in all paths from $u$ to $v$, or
determine that there is no such vertex (resp., edge). Georgiadis et al. [30]
show how to precompute the answers to all possible $2$-reachability queries in
$O(\min\\{n^{\omega}\log n,mn\\})$ time. The notion of $2$-reachability
naturally generalizes to $k$-reachability where the query asks for a set of at
most $(k-1)$ vertices (resp., edges) whose removal leaves $v$ unreachable from
$u$, or determine that there is no such set of vertices (resp., edges). For
the case of $k$-reachability with respect to edge-disjoint paths, Abboud et
al. [1] show how to precompute the answer for all pairs of vertices in
$O(\min\\{n^{\omega},mn\\})$ when $k=O(1)$, but only in the case of DAGs. For
the case of (non-necessarily acyclic) planar graphs, Łącki et al. [43] showed
an algorithm with $\widetilde{O}(n^{5/2}+n^{2}k)$ running time. Hence, there
are no non-trivial results on the $k$-reachability problem in general directed
graphs.

Abboud et al. [1] also considered a weaker version of $k$-reachability in
which they only distinguish whether there are $k$ disjoint paths, or less
(without reporting a set of at most $k-1$ vertices/edges that destroy all
paths from $u$ to $v$, if such a set exists). They show how to precompute all
such answers, in the case of vertex-disjoint paths, in $O((nk)^{\omega})$
time. This weaker version of the problem can also be solved with respect to
edge-disjoint paths by computing the value of all-pairs min-cut in
$O(m^{\omega})$ time [19] for general graphs and in $\widetilde{O}(n^{2})$
time for planar graphs [43].

The related problem of sensitivity oracles for strongly connected components
(SCCs) was considered by Georgiadis et al. [32]. Specifically they presented a
1-sensitivity oracle with $O(m)$ size and preprocessing time, that can answer
various SCC queries under the presence of single edge or vertex failures in
asymptotically optimal time. For instance they can test whether two vertices
$u,v$ are in the same SCC in $G-x$ in constant time, for query vertices $u,v$
and failed vertex or edge $x$, or they can report the SCCs of $G-x$ in $O(n)$
time. Baswana et al. [9], showed an $f$-sensitivity oracle with
$O(2^{f}n^{2})$ space, and $O(mn^{2})$ preprocessing time, that can report the
SCCs of $G-F$ in $O(2^{f}n\operatorname{polylog}n)$ time, where $F$ is a set
of failed vertices or edges, for $|F|\leq f$.

Reachability queries under edge or vertex failures can be also answered using
more powerful sensitivity oracles for shortest paths or approximate shortest
paths. For planar directed graphs there is no known $o(n^{2})$ space all-pairs
distance sensitivity oracle with $O(\operatorname{polylog}n)$ query time.
Baswana et al. [10] presented a single-source reachability oracle under single
edge or vertex failures with $O(n\operatorname{polylog}n)$ space and
construction time, that can report the length of the shortest path from $s$ to
$v$ in $G-x$ in $O(\log n)$ time, for query vertex $v$ and a failed vertex or
edge $x$. They extend their construction to work for the all-pairs variant of
the problem in $O(n^{3/2}\operatorname{polylog}n)$ preprocessing time and size
of the oracle, and answer queries in $O(\sqrt{n}\operatorname{polylog}n)$
time. Later on Charalampopoulos et al. [18] presented improved sensitivity
oracles for all-pairs shortest paths on planar graphs. Their sensitivity
oracle also handles multiple failures at the expense of a worse trade-off
between size and query time. For the all-pairs version of the problem, their
oracles have significantly worse bounds compared to the best known exact
distance oracles (without failures) for planar graphs. The best known exact
distance oracle for planar graphs with $O(\operatorname{polylog}n)$ query time
was presented recently by Charalampopoulos et al. [17]; it uses
$O(n^{1+\epsilon})$ space and has $O(n^{(3+\epsilon)/2})$ construction time.
However, we note that sensitivity distance oracles cannot answer
$2$-reachability queries.

Finally, note that we could in principle handle $f$-sensitivity queries with a
fully dynamic reachability or shortest-paths oracle with good worst-case
update and query bounds [22, 47]. However, not very surprisingly, this
approach rarely yields better bounds than the $f$-sensitivity solutions
tailored to handle only batches of failures.

In summary, there exist efficient fault-tolerant reachability oracles for
general digraphs with preprocessing time, size, and query time comparable to
the fastest known static reachability oracles (without failures). This is the
case, e.g., for the fault-tolerant reachability oracle and $2$-reachability
oracle of [30], which almost matches the $O(\min\\{mn,n^{\omega}\\})$ bound
for computing reachability without failures, and for the data structure for
SCCs under failures of [32], which has linear construction time and space, and
it is capable of answering queries in asymptotically optimal time. However,
and somehow surprisingly, such efficient fault-tolerant reachability oracles
and $2$-reachability oracles, i.e., oracles with preprocessing time, size, and
query time comparable to the fastest known static oracles (without failures)
are not known in the case of any basic problem on _planar directed graphs_.
Such oracles would implement some of the most important functionalities of
dominator trees, but for all possible sources at once. Since dominator trees
have several applications, including applications in planar digraphs, it seems
quite natural to ask whether such oracles exist.

An additional motivating factor for studying our problem is the large gap in
known and possible bounds between undirected and directed graphs for related
problems. For the case of undirected graphs, there exist nearly optimal
$f$-sensitivity oracles for answering connectivity queries under edge and
vertex failures. Duan and Pettie [24] presented a near-optimal preprocessing
$O(n\log{n})$-space $f$-sensitivity oracle that, for any set $F$ of up to $f$
edge-failures their oracle, spends $O(f\log f\log\log n)$ time to process the
failed edges and then can answer connectivity queries in $G\setminus F$ in
time $O(\log\log n)$ per query. This result is nearly optimal also for the
case of planar undirected graphs. In the same paper, the authors also present
near-optimal bounds for the case of vertex-failures. For general directed
graphs, it is clear that sensitivity oracles for all-pairs reachability cannot
achieve bounds anywhere close to the known bounds for sensitivity oracles for
connectivity in undirected graphs. While answering connectivity queries in
undirected graphs is a much simpler task than answering reachability queries
in digraphs, an intriguing question is whether there exists a general family
of directed graphs that admits fault-tolerant reachability oracles with bounds
close to the known results for sensitivity connectivity oracles in undirected
graphs, even for the case of a single failure.

#### Our results.

We answer the questions posed above affirmatively by presenting the first
_near-optimal_ – in terms of both time and space – oracle handling _all-pair-
type_ queries for _directed_ planar graphs and supporting any _single vertex
or single edge failure_. Specifically, we prove the following.

######  Theorem 1.1.

Let $G$ be a planar digraph. There exists an $O(n\log{n})$-space data
structure answering queries of the form ’’is there a $u\to v$ path in $G-x$‘‘,
where $u,v,x\in V$, in $O(\log{n})$ time. The data structure can be
constructed in $O(n\log^{2}{n}/\log\log{n})$ time.

We remark that previous data structures handling failures in
$O(\operatorname{polylog}n)$ time either work only for the single-source
version of the problem (see dominator trees, or [20] for two failures), or
work only on undirected graphs (see, e.g., [23, 24] for oracles for general
graphs, and [2, 13] for planar graphs), or achieve nearly linear space only
for dense graphs [55]. It is worth noting that for planar digraphs vertex
failures are generally more challenging than edge failures, since, whereas one
can easily reduce edge failures to vertex failures, the standard opposite
reduction of splitting a vertex into an in- and an out-vertex does not
preserve planarity.

In order to achieve our 1-sensitivity oracle, we develop the following two new
data structures that also work on general digraphs and can be of independent
interest:

  * •

Given a digraph $G$ and a directed path $P$ of $G$, we present a linear-space
data structure that, after preprocessing $G$ in $O(n+m\log m/\log\log m)$
time, can answer whether there exists a path from $u$ to $v$ in $G-x$ passing
through a vertex of $P$, for any query vertices $u,v\in V$ and $x\in
V\setminus V(P)$. In a sense, this result generalizes the dominator tree (a
tree $T$ rooted at a source-vertex $s$ such that a vertex $t$ is reachable
from $s$ in $G-x$ if and only if it is reachable in $T-x$) in the following
way. Note that a pair of dominator trees from and to $s$ can be used to
support queries of the form ’’is $u$ reachable from $v$ through a ’’hub‘‘ $s$
in $G-x$?‘‘, where $u,v,x\neq s$ are all query vertices and $s$ is fixed. Our
data structure allows to replace the single hub $s$ with any number of hubs
that form a directed path, provided that these hubs cannot fail. Since
dominator trees have numerous applications, as discussed before, we believe
that our generalization can find other applications as well.

  * •

We show that given a digraph $G$ and an assignment of real-valued labels to
the vertices of $G$, in $O(m+n(\log n\log\log n)^{2/3})$ time one can
construct a linear-space data structure that supports $O(1)$-time queries of
the form ’’what is the largest/smallest label in the strongly connected
component of $u$ in $G-x$?”, for any pair of query vertices $u,x\in V$.

By suitably extending our 1-sensitivity oracle, we obtain a nearly optimal
$2$-reachability oracle for planar digraphs, summarized as follows.

######  Theorem 1.2.

In $O(n\log^{6+o(1)}{n})$ time one can construct an
$O(n\log^{3+o(1)}{n})$-space data structure supporting the following queries
in $O(\log^{2+o(1)}{n})$ time. For $u,v\in V(G)$, either find some separating
vertex $x\notin\\{u,v\\}$ lying on all $u\to v$ paths in $G$, or declare $v$
2-reachable from $u$.

Our 1-sensitivity and $2$-reachability oracles, combined, extend several
supported operations of dominator trees to the all-pairs version of the
problem. For example, for any $u,v$, our data structures can identify the set
$X$ of all vertices (or edges) that appear in all paths from $u$ to $v$ in
$O(|X|\log^{2+o(1)}n)$ time by executing $O(|X|)$ $2$-reachability queries.
That is, a $2$-reachability query returns a vertex $x$ that appears in all
paths from $u$ to $v$, and all other vertices in $X\setminus x$ (if any)
appear either in all paths from $u$ to $x$ or in all paths from $x$ to $v$,
which we can identify by recursively executing $2$-reachability queries from
$u$ to $x$ and from $x$ to $v$, and eventually reconstruct the set $X$.

Whereas we achieve $\widetilde{O}(n)$ preprocessing time for both our oracles,
the main conceptual challenge lies in obtaining near-optimal space. However,
efficient construction of the used data structures, especially our
generalization of the dominator tree, proved to be a highly non-trivial task
as well.

#### Overview of our 1-sensitivity oracle.

As already discussed, it is sufficient to build a 1-sensitivity oracle for
single vertex failures as the case of edge failures reduces to the case of
vertex failures by applying edge-splitting on the edges of the graph (i.e.,
replacing each edge $zw$ by a new vertex $c$, and two edges $zc$ and $cw$).
Since $m=O(n)$ in planar graphs, this process does not increase the number of
vertices or edges significantly. The initial step of our approach is the use
of the basic555Thorup [54] also presented a more involved data structure that
allowed him to reduce query time to $O(1)$ while maintaining the preprocessing
time $O(n\log{n})$. However, this data structure significantly differs from
his basic $O(\log{n})$-query data structure in the fact that one needs to
represent reachability through separating directed paths $P$ “globally” in the
entire graph $G$, as opposed to only representing reachability through $P$
“locally” in the subgraph $H\subseteq G$ we recurse on. It is not clear if
this more sophisticated approach can be extended to handle vertex failures.
hierarchical decomposition approach introduced by Thorup [54]. For the problem
of constructing a reachability oracle (with no failures) this initial phase
allows one to focus on the following problem, at the expense of an increase by
a factor $O(\log n)$ in the preprocessing time, the size, and the query time
of the constructed oracle. Given a graph $G$ and a directed path $P$ of $G$,
construct a data structure that answers efficiently whether there is a path
from $u$ to $v$ containing any vertex of $P$, for any two vertices $u$ and
$v$. It is rather easy to obtain such a data structure with linear space and
preprocessing time that can answer the required queries in constant time.

Although we use the decomposition phase of [54] as an initial step in our
approach, the main difficulty in our problem is to build a data structure that
can efficiently answer whether there exists a path from $u$ to $v$ in $G-x$
that uses a vertex of a path $P$. In the presence of failed vertices this
becomes much more challenging, compared to reachability queries with no
failures, as the set of vertices of $P$ that are reachable from (or can
reached by) a vertex $w$, might be different under failures of different
vertices. Additionally, the case where the failed vertex appears on $P$
disconnects the path into two subpaths which we need to query. We cannot
afford to simply preprocess all such subpaths, as there can be as many as
$|P|=\Theta(n)$ of those for all possible failures of vertices on the path
$P$. We overcome these problems by using new insights, developing new
supporting data structures and further exploiting planarity.

We distinguish two cases depending on whether the failed vertex appears on $P$
or not. For each path $P$, we preprocess the graph to handle each case
separately.

To deal with the case where the failed vertex lies outside of $P$, we
identify, for the query vertices $u,v$ and failed vertex $x$, the earliest
(resp., latest) vertex on $P$ that $u$ can reach (resp., that can reach $v$)
in $G-x$. Call this vertex $first^{P}_{G-x}(u)$ (resp., $last^{P}_{G-x}(v)$).
Given these vertices it suffices to test whether $first^{P}_{G-x}(u)$ appears
no later than $last^{P}_{G-x}(v)$ on $P$. Recall from our previous discussion
that both these vertices depend on the failed vertex $x$. A useful notion
throughout the paper is the following. A path $Q$ between any two vertices
$w,z$ is called a _satellite_ path (with respect to $P$) if no vertex of $Q$
other than $w,z$ is a vertex of $P$, i.e., if $V(Q)\cap
V(P)\subseteq\\{w,z\\}$. On a very high level, we first develop a near-optimal
data structure that can identify in constant time for each vertex $v$ the
latest vertex $v^{\prime}\in V(P)$ that has a satellite path to $v$ in $G-x$.
The performance of the data structure relies on the efficient constructions of
dominator trees [6, 14, 25, 26] and their properties, as well as dynamic
orthogonal range-searching data structures [16]. Given $v^{\prime}$, we then
show that $last^{P}_{G-x}(u)$ is the latest vertex on $P$ that is in the same
SCC as $v^{\prime}$ in $G-x$. We generalize the problem of computing such a
vertex to the mentioned problem of efficiently finding a maximum-labeled
vertex in the SCC of $v$ in $G-x$, where $v,x\in V$ are query parameters. For
this problem we develop a near-optimal data structure with $O(1)$ query time.
Finally, we proceed with computing $first^{P}_{G-x}(u)$ analogously. The query
time in this case is $O(1)$.

In order to handle the case when the failed vertex $x$ is on $P$ we further
exploit planarity. We observe that by modifying the basic recursive
decomposition of Thorup to use fundamental cycle separators instead of root
path separators (this modification was previously used in e.g. [2, 45]), we
can assume that the endpoints of $P$ in fact lie on a single face of $G$. This
additional assumption enables us to achieve two important things. First we
show that after linear preprocessing, in $O(\log{n})$ time we can in fact
compute the earliest (latest) vertex of _any subpath of $P$_ reachable from
(that can reach) a query vertex $v\in V$ by a satellite path. Here the subpath
of interest is also a query parameter. Moreover, we introduce a concept of a
detour of $x$ to be a path that starts earlier and ends later than $x$ on $P$.
A minimal detour of $x$ is a detour that does not simultaneously start earlier
(on $P$) and end later (on $P$) that any other detour of $x$. We use planarity
to show that there can be at most two significantly different minimal detours
of any vertex $x\in V(P)$. Consequently, we show a linear time algorithm for
finding the two minimal detours for each vertex $x\in V(P)$. Finally, we
consider several possible scenarios of how the requested $u\to v$ path in
$G-x$ can interact with $P$ and $x$. In all of these cases we show that there
exists a certain canonical path consisting of $O(1)$ subpaths that are either
satellite paths, minimal detours, or subpaths of $P$. This allows us to test
for existence of a $u\to v$ path in $G-x$ with only $O(1)$ queries to the
obtained data structures.

Even though we are not able to reduce the query time in the case when $x$ lies
on the path $P$ to constant, this turns out not to be a problem. This is
because in order to answer a ’’global‘‘ query, we need only one such query and
$O(\log{n})$ constant-time queries to the data structures when $x$ is out of
the path. It follows that the query time of the whole reachability data
structure is $O(\log{n})$.

#### 2-reachability oracle.

The 2-reachability oracle is obtained by both extending and reusing the
1-sensitivity oracle. It is known that if the graph is strongly connected,
then checking whether vertex $v$ is $2$-reachable from $u$ can be reduced to
testing whether $v$ is reachable from $u$ under only $O(1)$ single-vertex
failures, which are easily computable from the dominator tree from an
arbitrary vertex of the graph [30]. This observation alone would imply a
2-reachability oracle for strongly connected planar digraphs within the
time/space bounds of our 1-sensitivity oracle.

However, for graphs with $k$ strongly connected components, a generalization
of this seems to require information from as many as $\Theta(k)$ dominator
trees to cover all possible $(u,v)$ query pairs.

Nevertheless, we manage to overcome this problem by using the same recursive
approach, and carefully developing the ’’existential‘‘ analog of the
1-sensitivity data structures handling failures either outside the separating
path $P$, or on the separating path $P$ when $P$‘s endpoints lie on a single
face of the graph. There is a subtle difference though; in the 2-reachability
oracle the recursive call is made only when $P$ contains no vertex that lies
on a $u\to v$ path; once we find a path $P$ containing a vertex that lies on
any $u\to v$ path we make no further recursive calls.

In the case of failures outside the path $P$, we prove that $O(1)$ single-
failure queries are sufficient to decide whether there exists $x\notin V(P)$
that destroys all $u\to v$ paths in $G$. Even though we use $\Theta(n)$
dominator trees to encode the information about which single-failure queries
we should issue to the $1$-sensitivity oracle (for any pair $u,v$ of query
vertices), our construction guarantees that the total size of these dominator
trees is $O(n)$.

When searching for vertices $x\in V(P)$ that lie on all $u\to v$ paths in $G$,
the reduction to asking few 1-sensitivity queries does not to work. Instead,
we take a substantially different approach. Roughly speaking, we simulate the
single-failure query procedure developed in the 1-sensitivity oracle for all
failing $x\in V(P)$ at once. We prove that deciding if for any such $x$ the
query to the 1-sensitivity oracle would return false can be reduced to a
generalization of a 4-dimensional orthogonal range reporting problem, where
the topology of one of the dimensions is a tree as opposed to a line. A simple
application of heavy-path decomposition [48] allows us to reduce this problem
to the standard 4-d orthogonal range reporting problem [38] at the cost of
$O(\log{n})$-factor slowdown in the query time compared to the standard case.
This turns out to be the decisive factor in the $O(\log^{2+o(1)}n)$ query time
and $O(n\log^{3+o(1)}{n})$ space usage of our 2-reachability oracle.

#### Organization of the paper.

In Section 2 we fix the notation and recall some important properties of
planar graphs. In Section 3 we give a quite detailed overview of Thorup‘s
construction and explain how we modify it to suit our needs. In Section 4 we
show how to make the reachability data structure from Section 3 to support
vertex failures. Apart from that, in Section 4 we also state and explain the
usage of our main technical contributions – Theorems 4.1, 4.3 and 4.4 – and
give a more detailed overview of how they are achieved. The detailed proofs of
these theorems can be found in Sections 6, 7 and 9, respectively. In Section 5
we review some useful properties of dominator trees. The 2-reachability data
structure is covered in Section 8.

##  2 Preliminaries

In this paper we deal with _directed_ simple graphs (_digraphs_). We often
deal with multiple different graphs at once. For a graph $G$, we let $V(G)$
and $E(G)$ denote the vertex and edge set of $G$, respectively. If
$G_{1},G_{2}$ are two graphs, then $G_{1}\cup G_{2}=(V(G_{1})\cup
V(G_{2}),E(G_{1})\cup E(G_{2}))$ and $G_{1}\cap G_{2}=(V(G_{1})\cap
V(G_{2}),E(G_{1})\cap E(G_{2}))$. Even though we work with digraphs, some
notions that we use, such as connected components, or spanning trees, are only
defined for undirected graphs. Whenever we use these notions with respect to a
digraph, we ignore the directions of the edges.

Let $G=(V,E)$ be a digraph. We denote by $uv\in E$ the edge from $u$ to $v$ in
$G$. A graph $G^{\prime}$ is called a subgraph of $G$ if
$V(G^{\prime})\subseteq V(G)$ and $E(G^{\prime})\subseteq E(G)$. For
$S\subseteq V(G)$, we denote by $G[S]$ the _induced subgraph_ $(S,\\{uv:uv\in
E(G),\\{u,v\\}\subseteq S\\})$. Given a digraph $G$, we denote by $G^{R}$ the
digraph with the same set of vertices as $G$ and with all of the edges
reversed compared to the orientation of the corresponding edges in $G$. That
is, if $G$ contains an edge $uv$, $G^{R}$ contains an edge $vu$ and vice
versa. We say that $G^{R}$ is the _reverse graph_ of $G$. For any $X\subseteq
V$ we define $G-X=G[V\setminus X]$. For $x\in V$, we write $G-x$ instead of
$G-\\{x\\}$.

A _path_ $P\subseteq G$ is a subgraph whose edges $E(P)$ can be ordered
$e_{1},\ldots,e_{k}$ such that if $e_{i}=u_{i}v_{i}$, then for $i=2,\ldots,k$
we have $u_{i}=v_{i-1}$. Such $P$ is also called a $u_{1}\to v_{k}$ path. We
also sometimes write $P=u_{1}u_{2}\ldots u_{k}$. A path $P$ is _simple_ if
$u_{i}\neq u_{j}$ for $i\neq j$. For a simple path $P=u_{1}\ldots u_{k}$ we
define an order $\prec_{P}$ on the vertices of $P$. We write $v\prec_{P}w$ for
$v=u_{i}$ and $w=u_{j}$ if $i<j$. If $u\prec_{P}v$, we also say that $u$ is
_earlier_ on $P$ than $v$, whereas $v$ is _later_ than $u$ on $P$. We denote
by $P[u_{i},u_{j}]$ the unique subpath of $P$ from $u_{i}$ to $u_{j}$.
Similarly, let $P(u_{i},u_{j})$ be the subpath of $P$ from the vertex
following $u_{i}$ to the vertex preceding $u_{j}$ on $P$. For $u,v\in V$, we
say that $v$ is _reachable_ from $u$ if there exists a $u\to v$ path in $G$.
We call $v$ _2-reachable_ from $u$ if there exist two internally vertex-
disjoint $u\to v$ paths in $G$. $u$ and $v$ are _strongly connected_ if there
exist both paths $u\to v$ and $v\to u$ in $G$. A _non-oriented path_
$P^{\prime}\subseteq G$ is a subgraph that would become a path if we changed
the directions of some of its edges. If $P_{1}=u\to v$ is a (potentially non-
oriented) path and $P_{2}=v\to w$ is a (non-oriented) path, their
concatenation $P_{1}P_{2}=u\to w$ is also a (non-oriented) path.

We sometimes use trees, which can be rooted or unrooted. If a tree $T$ is
rooted, we denote by $T[v]$ the _subtree_ of $T$ rooted in one of its vertices
$v$. We denote by $T[u,v]$ the path between $u$ and $v$ on $T$, by $T(u,v]$
(resp., $T[u,v)$) the path between $u$ and $v$ on $T$, excluding $u$ (resp.,
excluding $v$). Analogously, we use $T(u,v)$ to denote the path between $u$
and $v$ on $T$, excluding $u$ and $v$. For any tree $T$, we use the notation
$t(v)$ to refer to the parent of node $v$ in $T$. If $v$ is the root of the
tree, then $t(v)=v$. To avoid cumbersome notation we sometimes write $w\in
T[v]$ when we formally mean $w\in V(T[v])$, $w\in T[u,v]$ when $w\in
V(T[u,v])$ and so on. If $T\subseteq G$ is a spanning tree of a connected
graph $G$, then for any $uv\in E(G)\setminus E(T)$ the _fundamental cycle_ of
$uv$ wrt. $T$ is a subgraph of $G$ that consists of the unique non-oriented
simple $u\to v$ path in $T$ and the edge $uv$.

#### Plane graphs.

A _plane embedding_ of a graph is a mapping of its vertices to distinct points
and of its edges to non-crossing curves in the plane. We say that $G$ is
_plane_ if some embedding of $G$ is assumed. A _face_ of a connected plane $G$
is a maximal open connected set of points that are not in the image of any
vertex or edge in the embedding of $G$. There is exactly one _unbounded_ face.
The _bounding cycle_ of a bounded (unbounded, respectively) face $f$ is a
sequence of edges bounding $f$ in clockwise (counterclockwise, respectively)
order. Here, we ignore the directions of edges. An edge can appear in a
bounding cycle at most twice. An embedding of a planar graph (along with the
bounding cycles of all faces) can be found in linear time [36]. A plane graph
$G$ is _triangulated_ if all its faces‘ bounding cycles consist of $3$ edges.
Given the bounding cycles of all faces, a plane graph can be triangulated by
adding edges inside its faces in linear time.

A graph $G^{\prime}$ is called a _minor_ of $G$ if it can be obtained from $G$
by performing a sequence of edge deletions, edge contractions, and vertex
deletions. If $G$ is planar then $G^{\prime}$ is planar as well. By the Jordan
Curve Theorem, a simple closed curve $C$ partitions $\mathbb{R}^{2}\setminus
C$ into two connected regions, a bounded one $B$ and an unbounded one $U$. We
say that a set of points $P$ is _strictly inside_ (_strictly outside_) $C$ if
and only if $P\subseteq B$ ($P\subseteq U$, respectively). $P$ is _weakly
inside_ (_weakly outside_) iff $P\subseteq B\cup C$ ($P\subseteq U\cup C$,
respectively). If $G$ is plane then the fundamental cycle of $uv$ corresponds
to a simple closed curve in the plane. We often identify the fundamental cycle
with this curve.

######  Lemma 2.1 (e.g., [40]).

Let $G=(V,E)$ be a connected triangulated plane graph with $n$ vertices. Let
$T$ be a spanning tree of $G$. Let $w:V\to\mathbb{R}_{\geq 0}$ be some
assignment of weights to the vertices of $G$. Set $W:=\sum_{v\in V}w(v)$.
Suppose that for each $v\in V$ we have $w(v)\leq\frac{1}{4}W$.

There exists such $uv\in E\setminus E(T)$ that the total weight of vertices of
$G$ lying strictly on one side of the fundamental cycle of $uv$ wrt. $T$ is at
most $\frac{3}{4}W$. The edge $uv$ can be found in linear time.

##  3 The Reachability Oracle by Thorup

In this section we describe the basic reachability oracle of Thorup [54] that
we will subsequently extend to support single vertex failures. His result can
be summarized as follows.

######  Theorem 3.1 ([54]).

Let $G$ be a directed planar graph. One can preprocess $G$ in $O(n\log{n})$
time so that arbitrary reachability queries are supported in $O(\log{n})$
time.

######  Definition 3.2 ([54]).

A $2$-layered spanning tree $T$ of a digraph $H$ is a rooted spanning tree
such that any non-oriented path in $T$ from the root is a concatenation of at
most two directed paths in $H$.

We will operate on graphs with some _suppressed vertices_. Those suppressed
vertices will guarantee certain useful topological properties of our plane
graphs, but will otherwise be forbidden to be used from the point of view of
reachability. In other words, when answering reachability queries we will only
care about directed paths that do not go through suppressed vertices.

######  Remark 3.3.

Our description differs from that of Thorup in the fact that we allow $O(1)$
suppressed vertices (where Thorup needed only one that was additionally always
the root of the spanning tree, and no balancing of suppressed vertices was
needed), and we insist on using simple cycle separators (whereas Thorup‘s
separators consisted of two root paths). Whereas using cycle separators does
not make any difference for reachability, we rely on them later when we handle
single vertex failures.

######  Lemma 3.4 ([54]).

Let $G=(V,E)$ be a connected digraph. In linear time we can construct digraphs
$G_{0},\ldots,G_{k-1}$, where $G_{i}=(V_{i},E_{i})$, and $A_{i}\subseteq
V_{i}$ is a set of suppressed vertices, $|A_{i}|\leq 1$, and their respective
spanning trees $T_{i}$, and a function $\imath:V\to\\{0,\ldots,k-1\\}$ such
that:

  1. 1.

The total number of edges and vertices in all $G_{i}$ is linear in $|V|+|E|$.

  2. 2.

Each $G_{i}$ is a minor of $G$, and $G_{i}-A_{i}$ is a subgraph of $G$.

  3. 3.

For any $u,v\in V$ and any directed path $P=u\to v$, $P\subseteq G$ if and
only if $P\subseteq G_{\imath(u)}-A_{\imath(u)}$ or $P\subseteq
G_{\imath(u)-1}-A_{\imath(u)-1}$.

  4. 4.

Each spanning tree $T_{i}$ is $2$-layered.

The basic reachability data structure of Thorup [54] can be described as
follows. Observe that by Lemma 3.4 $v$ is reachable from $u$ in $G$ (where
$u,v\in V$) if and only if it is reachable from $u$ in either
$G_{\imath(u)}-A_{\imath(u)}$ or $G_{\imath(u)-1}-A_{\imath(u)-1}$. Moreover,
all the graphs $G_{i}$ in Lemma 3.4, being minors of $G$, are planar as well.
Therefore, by applying Lemma 3.4, the problem is reduced to the case when (1)
a planar graph $G=(V,E)$ has a 2-layered spanning tree $T$, (2) we are only
interested in reachability without going through some set of $O(1)$ (in fact,
at most $5$, as we will see) suppressed vertices $A$ of $G$. Under these
assumptions, the problem is solved recursively as follows.

If $G$ has constant size, or has only suppressed vertices, we compute its
transitive closure so that queries are answered in $O(1)$ time. Otherwise, we
apply recursion. We first temporarily triangulate $G$ by adding edges and
obtain graph $G^{\Delta}$. Note that $T$ is a 2-layered spanning tree of
$G^{\Delta}$ as well.

######  Fact 3.5.

Let $G=(V,E)$ be a connected plane digraph. Let $T$ be a 2-layered spanning
tree of $G$ rooted at $r$. Let $uv\in E\setminus E(T)$. Let $V_{1}$ (resp.,
$V_{2}$) be the subset of $V$ strictly inside (resp., strictly outside) the
fundamental cycle $C_{uv}$ of $uv$ wrt. $T$. Let $S_{uv}$ be the non-oriented
path $C_{uv}-uv$.

Let $G^{\prime}$ ($T^{\prime}$) be obtained from $G$ ($T$) by contracting (the
edges of) $S_{uv}$ into a single vertex $r^{\prime}$. Then for $i=1,2$,
$T^{\prime}[V_{i}\cup\\{r^{\prime}\\}]$ is a 2-layered spanning tree of
$G^{\prime}[V_{i}\cup\\{r^{\prime}\\}]$.

Using Lemma 2.1, we compute in linear time a balanced fundamental cycle
separator $C_{ab}$, where $ab\in E(G^{\Delta})\setminus E(T)$. Let $A$ be the
set of suppressed vertices of $G$. The weights assigned to vertices depend on
the size of $A$: if $|A|\leq 4$ then we assign weights $1$ uniformly to all
vertices of $G$, and otherwise we assign unit weights to the vertices of $A$
only (the remaining vertices $V$ get weight $0$). Let the non-oriented path
$S_{ab}=C_{ab}-ab$ be called _the separator_. Let
$V_{1},V_{2},G^{\prime},T^{\prime}$ and $r^{\prime}$ be defined as in Fact
3.5.

Note that for any $u,v\in V$, a $u\to v$ path in $G-A$ can either go through a
vertex of $S_{ab}$, or is entirely contained in exactly one $G[V_{i}]-A$, for
which $\\{u,v\\}\subseteq V_{i}$ holds. We deal with these two cases
separately. Since $G[V_{i}]\subseteq G^{\prime}[V_{i}\cup\\{r^{\prime}\\}]$,
queries about a $u\to v$ path not going through $S_{ab}$ can be delegated to
the data structures built recursively on each
$G^{\prime}[V_{i}\cup\\{r^{\prime}\\}]$ with suppressed set $A_{i}=(A\cap
V_{i})\cup\\{r^{\prime}\\}$. By Fact 3.5,
$G^{\prime}[V_{i}\cup\\{r^{\prime}\\}]$ has a 2-layered spanning tree
$T^{\prime}[V_{i}\cup\\{r^{\prime}\\}]$ rooted in $r^{\prime}$. Moreover, a
path $u\to v$ exists in $G[V_{i}]-A$ if and only if a path $u\to v$ not going
through a suppressed set $A_{i}$ exists in
$G^{\prime}[V_{i}\cup\\{r^{\prime}\\}]$. Note that since $S_{ab}$ does not
necessarily go through any of the vertices of $A$, $A_{i}$ might be larger
than $A$ by a single element – this is why balancing of suppressed vertices is
needed. Hence, indeed recursion can be applied in this case.

Paths $u\to v$ going through $V(S_{ab})$ in $G-A$ are in turn handled as
follows. Since $T$ is 2-layered, $S_{ab}$ can be decomposed into at most 4
edge-disjoint directed paths in $G$. Consequently, $S_{ab}-A$ can be split
into at most $4+|A|$ edge-disjoint directed paths in $G-A$. Next, we take
advantage of the following lemma.

######  Lemma 3.6 ([49, 54]).

Let $H$ be a directed graph and let $P\subseteq H$ be a simple directed path.
Then, in linear time we can build a data structure that supports constant-time
queries about the existence of a $u\to v$ path that necessarily goes through
$V(P)$.

The above lemma is based on the following simple fact that will prove useful
later on.

######  Fact 3.7 ([49, 54]).

Let $H$ be a digraph. Let $P\subseteq H$ be a simple directed path. Denote by
$first_{H}^{P}(u)$ the earliest vertex of $P$ _reachable from_ $u$ in $H$.
Denote by $last_{H}^{P}(v)$ the latest vertex of $P$ that _can reach_ $v$ in
$H$. Then there exists a $u\to v$ path in $H$ going through $V(P)$ iff
$first_{H}^{P}(u)\preceq_{P}last_{H}^{P}(v)$.

Consequently, by building at most $4+|A|$ data structures of Lemma 3.6, we can
check whether $v$ is reachable from $u$ through $V(S_{ab})$ in $G-A$ in
$O(1+|A|)$ time.

######  Lemma 3.8.

At each recursive call, the size of the suppressed set $A$ is at most $5$.

###### Proof.

We apply induction on the level of the recursive call that is passed graph $G$
with suppressed set $A$. In the first recursive call (level $0$) after
applying Lemma 3.4, $A$ has size at most $1$.

Let the level of the recursive call be at least $1$. In the parent call the
suppressed set $A^{\prime}$ had size at most $5$. If $|A^{\prime}|=5$, then
the balanced cycle separator $C_{ab}$ put at most $3$ vertices of $A^{\prime}$
strictly on one side of $C_{ab}$. Since the entire set $V(C_{ab})$ was
subsequently contracted into a single vertex that got suppressed, $A$ has size
at most $3+1=4$.

On the other hand, if $|A^{\prime}|\leq 4$, then clearly
$|A|\leq|A^{\prime}|+1\leq 5$. ∎

######  Lemma 3.9.

The depth of the recursion is $O(\log{n})$.

###### Proof.

If the cycle separator computed at the parent call balanced all the vertices
of the graph $G^{\prime}$ with suppressed set $A^{\prime}$ and $n$ vertices,
then $G$ has at most $\frac{3}{4}n+1$ vertices.

However, if $|A^{\prime}|=5$, then $G$ might have nearly $n$ vertices. But in
this case $|A|\leq 4$, so the in the children recursive calls the graphs will
certainly have no more than $\frac{3}{4}n$ vertices.

This proves that at each recursive call the number of vertices is reduced by a
constant factor compared to the grandparent call, i.e., the depth of the
recursion tree is $O(\log{n})$. ∎

At each recursive call of the data structure‘s construction procedure we use
only linear preprocessing time. Observe that at each recursive level the total
number of vertices in all graphs of that level is linear: there are at most
$n$ vertices that are not suppressed and each of these vertices resides in a
unique graph of that level. Since each graph has to have at least one non-
suppressed vertex, the number of graphs on that level is also at most $n$.
Therefore, given that $|A|=O(1)$ in every recursive call, the sum of sizes of
the graphs on that level is $O(n)$. By Lemma 3.9, we conclude that the total
time spent in preprocessing is $O(n\log{n})$.

In order to answer a query whether an $u\to v$ path exists, we only need to
query $O(\log{n})$ data structures of Lemma 3.6 handling queries about
reachability through a directed path.

##  4 Reachability Under Failures

In this section we explain how to modify the data structure discussed in
Section 3 to support queries of the form ’’is $v$ reachable from $u$ in
$G-x$?‘‘, where $u,v,x\in V$ are distinct query parameters.

First recall that, by Lemma 3.4, each path $P=u\to v$ exists in $G$ if and
only if it exists in either $G_{\imath(u)}-A_{\imath(u)}$ or
$G_{\imath(u)-1}-A_{\imath(u)-1}$. This, in particular, applies to paths $P$
avoiding $x$. As a result, $v$ is reachable from $u$ in $G-x$ if and only if
$v$ is reachable from $u$ in either $G_{\imath(u)}-A_{\imath(u)}-x$ or
$G_{\imath(u)-1}-A_{\imath(u)-1}-x$. That being said, we can again concentrate
on the case when $G$ has a 2-layered spanning tree and we only care about
reachability in $G-A$, where $A\subseteq V$ has size $O(1)$.

We follow the recursive approach of Section 3. The only difference lies in
handling paths in $G-A$ going through the separator $S_{ab}$. Ideally, we
would like to generalize the data structure of Lemma 3.6 so that single-vertex
failures are supported. However, it is not clear how to do it in full
generality. Instead, we show two separate data structures, which, when
combined, are powerful enough to handle paths going through a _cycle_
separator.

Recall that $S_{ab}-A$ can be decomposed into $O(1)$ simple directed paths
$P_{1},\ldots,P_{k}$ in $G-A$ that can only share endpoints. Denote by
$D\subseteq V(S_{ab})$ the set of endpoints of these paths. Suppose we want to
compute whether there exists a $u\to v$ path $Q$ in $G-A-x$ that additionally
goes through some vertex of $S_{ab}$. We distinguish several cases.

1. Suppose that $x\in D$. Recall that there exist only $O(1)$ such vertices $x$. Moreover, $S_{ab}-A-x$ can be decomposed into $O(1)$ simple paths in $G-A-x$. Hence, for each such $x$, we build $O(1)$ data structures of Lemma 3.6 to handle reachability queries through $S_{ab}$ in $G-A-x$ exactly as was done in Section 3. The preprocessing is clearly linear and the query time is $O(1)$ in this case.

2. Now suppose $x\notin D$ and there exists such $P_{i}$ that $V(Q)\cap V(P_{i})\neq\emptyset$ and $x\notin V(P_{i})$. Paths of this kind are handled using the following theorem (for $G:=G-A$, $P:=P_{i}$) proved in Section 6.

######  Theorem 4.1.

Let $G$ be a digraph and let $P\subseteq G$ be a simple directed path. In
$O\left(m\frac{\log{n}}{\log\log{n}}\right)$ time one can build a linear-space
data structure that can decide, for any $u,v\in V$, and $x\notin V(P)$, if
there exists a $u\to v$ path going through $V(P)$ in $G-x$. Such queries are
answered in $O(1)$ time.

3. The last remaining case is when none of the above cases apply. This means that $x\notin D$ and for all $P_{i}$ either $Q$ does not go through $V(P_{i})$ or $x\in V(P_{i})$. Since $V(P_{i})\cap V(P_{j})\subseteq D$ for all $j\neq i$, there can be at most one such $i$ that $x\in V(P_{i})$. For all $j\neq i$, $Q$ does not go through $V(P_{j})$. On the other hand, since $Q$ goes through $S_{ab}$, it in fact has to go through $V(P_{i})$.

######  Lemma 4.2.

Let $\bar{V_{i}}=V\setminus V(S_{ab})\cup V(P_{i})$. Then the endpoints of
$P_{i}$ lie on a single face of the component of $G[\bar{V_{i}}]-A$ that
contains $P_{i}$.

By Lemma 4.2, the last case can be handled using the following theorem proved
in Section 7.

###### Proof.

Since $C_{ab}$ is a cycle separator, we can also view $C_{ab}$ as a closed
curve that does not cross any edges (but can follow the edges) of $G-A$ and
has (the embedding of) each $P_{i}$ as a contiguous part. After removing
vertices $V(S_{ab})\setminus V(P_{i})$ from $G-A$, the part of the curve that
does not correspond to $P_{i}$ connects the endpoints of $P_{i}$ and does not
intersect (the embedding of) any other vertices or edges of
$G[\bar{V_{i}}]-A$. Hence, this part lies inside a single face of the
component of $G[\bar{V_{i}}]-A$ that contains $P_{i}$. We conclude that the
endpoints of $P_{i}$ lie on that single face. ∎

######  Theorem 4.3.

Let $G$ be a plane digraph and let $P\subseteq G$ be a simple path whose
endpoints lie on a single face of $G$. In linear time one can build a data
structure that can compute in $O(\log{n})$ time, whether there exists a $u\to
v$ path going through $V(P)$ in $G-x$, where $u,v\in V$ and $x\in V(P)$.

In order to prove Theorem 1.1, first note that the preprocessing time of our
data structure is $O(n\log^{2}{n}/\log\log{n})$, since all the data structures
of Lemma 3.6, and Theorems 4.1 and 4.3 can be constructed in
$O(n\log{n}/\log\log{n})$ time for each input graph of the recursion. Since
all these data structures use only linear space, the total space used is
$O(n\log{n})$. To analyze the query time, observe that similarly to Section 3,
we only query $O(\log{n})$ ’’reachability through a path‘‘ data structures.
All of them, except of the data structure of Theorem 4.3, have constant query
time. However, the data structure of Theorem 4.3 is only used to handle the
case when $x\in V(S_{ab})$. Observe that for any $w\in V$ there is no more
than one node in the recursive data structure such that $w$ is a vertex of the
respective separator $S_{ab}$. As a result, we only need to perform a single
query to a data structure of Theorem 4.3.

#### Overview of the ’’failed vertex out of $P$‘‘ data structure of Theorem
4.1.

To deal with this case, we identify, for the query vertices $u,v$ and failed
vertex $x$, the earliest (latest) vertex $first^{P}_{G-x}(u)$
($last^{P}_{G-x}(v)$, resp.) on $P$ that $u$ can reach (that can reach $v$,
resp.) in $G-x$. Given those vertices, by Fact 3.7, it suffices to test
whether $first^{P}_{G-x}(u)\preceq_{P}last^{P}_{G-x}(v)$. However, it comes at
no surprise that $first^{P}_{G-x}(u)$ and $last^{P}_{G-x}(v)$ depend on the
failed vertex $x$. In the remaining part of this overview we only consider
computing $last^{P}_{G-x}(v)$ (computing $first^{P}_{G-x}(u)$ is symmetrical).

A path $Q$ between any two $w,z\in V$ is called a _satellite_ path (with
respect to $P$) if no vertex of $Q$ other than $w,z$ is a vertex of $P$. Let
$last^{*P}_{G-x}(v)$ denote the latest vertex on $P$ that can reach $v$ in
$G-x$ using a satellite path. The first step to find $last^{P}_{G-x}(v)$ is to
efficiently compute $last^{*P}_{G-x}(v)$.

Let $P=p_{1}\ldots p_{\ell}$. For each $p_{i}$ we first identify all the
vertices $w$ for which $p_{i}$ is the latest vertex on $P$ that can reach $w$
with a satellite path, which we refer to as the $i$-th layer $L_{i}$. We also
compute all the possible failed vertices $x$ that can fail all paths from
$p_{i}$ to $w$ in $G[L_{i}\cup\\{p_{i}\\}]$; let us call those vertices the
$(p_{i},w)$-cut-points. We use dominator trees for a compact tree
representation of the $(p_{i},w)$-cut-points for all vertices $w\in L_{i}$.
While the division of $V\setminus V(P)$ into layers alone allows us to compute
$last^{*P}_{G-x}(v)$ in several possible query cases, the difficult case is
when the failed vertex $x$ is one of the $(p_{i},v)$-cut-points. We prove that
this case can be solved by (1) identifying, during the preprocessing, for each
possible $(p_{i},w)$-cut-point $c$, the latest vertex $p_{j}$ of $P$,
$p_{j}\prec p_{i}$, that has a satellite path to $c$ avoiding all
$(p_{i},c)$-cut-points (we call $p_{j}$ the rescuer of $c$), and (2) computing
(during the query) the latest rescuer of all $(p_{i},v)$-cut-points $c$ that
are not $(p_{i},x)$-cut-points.

The main challenge in (1) is efficient preprocessing. We cannot afford to
execute traversals for identifying the existence of such paths. To overcome
this difficulty, we leverage the properties of the dominator tree used for
representing all $(p_{i},w)$-cut-points, combined with a use of a dynamic two-
dimensional point reporting data structure [16]. The combination of those data
structures allows us to compute the rescuers for all vertices in $O(n\log
n/\log\log n)$ total time. To efficiently perform step (2) during the query,
it is enough to preprocess the dominator tree of $G[L_{i}\cup\\{p_{i}\\}]$
with vertices labeled with their rescuers and find the maximum labeled
vertices on a $x$-to-$v$ path in that tree. This can be done in $O(1)$-time
after linear preprocessing [21].

Finally, we show that $last^{P}_{G-x}(v)$ is the latest vertex of $P$ that is
strongly connected to $last^{*P}_{G-x}(v)$ in $G-x$. Given
$last^{*P}_{G-x}(v)$, one could identify $last^{P}_{G-x}(v)$ in
$O(\log|V(P)|)$ time with a binary search on $p_{k}\in P$ by answering
efficiently queries ’’are $p_{k}$ and $last^{*P}_{G-x}(v)$ strongly connected
in $G-x$?” using the data structure of [32]. However, this results in $O(\log
n)$ query time for each path $P$, while we are aiming at constant query time
per path. We improve this bound by showing in Section 9 that such queries can
be answered in $O(1)$ time, by means of the following non-trivial extension of
the framework in [32], which we believe might be of independent interest.

######  Theorem 4.4.

Given a digraph $G$ and an assignment $f:V\to\mathbb{R}$ of labels to the
vertices of $G$, we can preprocess $G$ in $O(m+n(\log n\log\log n)^{2/3})$
time, so that the following queries are supported in $O(1)$ time. Given
$x,v\in V(G)$, find a vertex with the maximum label in the SCC of $v$ in
$G-x$.

#### Overview of the ’’failed vertex on $P$‘‘ data structure of Theorem 4.3.

In order to handle this case we exploit planarity extensively. Let
$P=p_{1}\ldots p_{\ell}$. We define for each vertex $p_{k}=x\in V(P)$ a
_detour_ of $x$ to be a $p_{i}\to p_{j}$ satellite path, where $i<k<j$. A
_minimal detour_ of $x$ is such a detour $p_{i}\to p_{j}$ of $x$ that no
$p_{i^{\prime}}\to p_{j^{\prime}}$ detour of $x$ such that $i\leq
i^{\prime}\leq j^{\prime}\leq j$ and $j^{\prime}-i^{\prime}<j-i$ exists. Since
$p_{1}$ and $p_{\ell}$ lie on a single face of $G$ we show that there are at
most two non-equivalent (we identify a detour with a pair of its endpoints)
minimal detours of any vertex $x\in V(P)$. Moreover, we show a linear time
algorithm for finding these minimal detours for each vertex $x\in V(P)$.

Similarly as in the data structure of Theorem 4.1, we would like to construct
the requested $u\to v$ path $Q$ in $G-x$ of ’’pieces‘‘ that are either
satellite paths, subpaths of $P$, or paths between strongly connected
vertices. Since $x$ necessarily lies on $P$, the sets of satellite paths in
$G$ and $G-x$ are the same, i.e., the satellite paths do not depend on the
failed $x$. However, removing any $x\in V(P)$ from the graph breaks $P$ into
two parts $P[p_{1},p_{k-1}],P[p_{k+1},p_{\ell}]$. Thus, to be able to take
advantage of Fact 3.7, it seems necessary that we efficiently compute
$first^{*P}_{G}(u,p_{1},p_{k-1})$ ($last^{*P}_{G}(v,p_{1},p_{k-1})$), defined
as the earliest (latest, resp.) vertex on $P[p_{1},p_{k-1}]$ that $u$ can
reach (that can reach $v$, resp.) by a satellite path in $G$. Analogously we
need earliest (latest) vertices on the suffix subpaths of the form
$P[p_{k+1},p_{\ell}]$ that can be reached (can reach, resp.) by query
vertices. Unfortunately, it is not clear how to preprocess a general digraph
$G$ in nearly linear time so that such queries are supported in
polylogarithmic time. To circumvent this problem, we again use the fact that
$p_{1}$ and $p_{\ell}$ lie on a single face of $G$. Then cutting $G$ along $P$
yields two plane graphs $G_{1},G_{2}$ such that the path $P$ is a contiguous
part of a single face of both $G_{1}$ and $G_{2}$. Since a satellite path is
entirely in $G_{1}$ or $G_{2}$, we can deal with them separately. We show that
by extending $G_{i}$ with a tree of auxiliary vertices and building the
optimal reachability oracle [35] on it, we can find the vertices
$first^{*P}_{G}(u,p_{a},p_{b})$, $last^{*P}_{G}(v,p_{a},p_{b})$ for any
$p_{a},p_{b}$ in $O(\log{n})$ time using a variation of binary search.

Finally, given all the auxiliary data structures and tools, we show how to
answer ’’is there a $u\to v$ path $Q$ in $G-x$‘‘ queries in $O(\log{n})$ time.
To this end, we distinguish several scenarios depending on the possible
interactions of $Q$ with $P$. Let $enter({Q})$ (resp., $leave({Q})$) be the
first (resp., last) vertex on $Q$ that appears on $P$. We consider four cases
depending on whether $enter({Q})$ and $leave({Q})$ appear earlier or later
than $x$ on $P$. In each case we concentrate on looking for a certain
’’canonical‘‘ path that visits earliest/latest possible vertices on both sides
of $x$ on $P$ and jumps between the sides of $x$ using minimal detours. All in
all, we can limit ourselves to paths consisting of $O(1)$ subpaths of a very
special form that can be handled by our auxiliary data structures.

#### Finding the maximum label in an SCC under failures.

In order to obtain the general data structure of Theorem 4.4, we exploit the
framework developed in [32]. We extend this framework to identify the
minimum/maximum label in any single SCC in $G-x$, except of the one SCC that
contains an arbitrary but fixed vertex $s$. To deal with this case, we show
how we can precompute the maximum value in the SCC of $s$ in $G-x$, for all
possible failures $x$, via a reduction to a special case of offline two-
dimensional range minimum queries, which can be further reduced to decremental
one-dimensional range minimum queries [56].

##  5 Dominators in Directed Graphs

In this section we review the dominator trees and their properties.

A _flow graph_ is a directed graph with a start vertex $s$, where all vertices
are reachable from $s$. Let $G_{s}$ be a flow graph with start vertex $s$. A
vertex $u$ is a _dominator_ of a vertex $v$ ($u$ _dominates_ $v$) if every
path from $s$ to $v$ in $G_{s}$ contains $u$; $u$ is a _proper dominator_ of
$v$ if $u$ dominates $v$ and $u\not=v$. Let _dom $(v)$_ be the set of
dominators of $v$. Clearly, _dom_ $(s)$ $=\\{s\\}$ and for any $v\neq s$ we
have that $\\{s,v\\}\subseteq$ _dom $(v)$_: we say that $s$ and $v$ are the
_trivial dominators_ of $v$ in the flow graph $G_{s}$. The dominator relation
is reflexive and transitive. Its transitive reduction is a rooted tree [3,
42], known as the _dominator tree_ $D$: $u$ dominates $v$ if and only if $u$
is an ancestor of $v$ in $D$. If $v\not=s$, the parent of $v$ in $D$, denoted
by $d(v)$, is the _immediate dominator_ of $v$: it is the unique proper
dominator of $v$ that is dominated by all proper dominators of $v$. Similarly,
we can define the dominator relation in the flow graph $G_{s}^{R}$, and let
$D^{R}$ denote the dominator tree of $G_{s}^{R}$. We also denote the immediate
dominator of $v$ in $G_{s}^{R}$ by $d^{R}(v)$. Lengauer and Tarjan [41]
presented an algorithm for computing dominators in $O(m\alpha(m,n))$ time for
a flow graph with $n$ vertices and $m$ edges, where $\alpha$ is a functional
inverse of Ackermann‘s function [52]. Subsequently, several linear-time
algorithms were discovered [6, 14, 25, 26]. We apply the tree notation
introduced earlier on for referring to subtrees and paths to dominator trees
as well.

######  Lemma 5.1 ([28]).

Let $G$ be a flow graph with start vertex $s$ and let $v\not=s$. Let $w$ be
any vertex that is not a descendant of $v$ in $D$. All simple paths in $G$
from $w$ to any descendant of $v$ in $D$ must contain $v$.

######  Lemma 5.2 ([33]).

For each $zw\in E(G_{s})$, where $z\neq s$, $z$ is a descendant of $d(w)$ in
$D$.

######  Lemma 5.3.

Let $G$ be a flow graph with start vertex $s$ and let $v\not=s$ be a non-leaf
in the dominator tree $D$ of $G$. There exists a simple path in $G[D[v]]$ from
$v$ to any $w\in D[v]$.

###### Proof.

Assume there is no path from $v$ to some vertex $w\in D[v]$ in $G[D[v]]$.
First, notice that there is a path from $v$ to $w$ in $G$, since $w$ is
reachable from $s$ in $G$, but not $G-v$. Hence, all simple paths from $v$ to
$w$ in $G$ contain vertices in $V\setminus D[v]$. Take such a path $Q$, and
let $z$ be any vertex from $V\setminus D[v]$, and let $Q^{\prime}$ be the
subpath from $z$ to $w$. Since $Q$ is simple and $v$ appears as the first
vertex on $Q$, $v\notin V(Q^{\prime})$. By Lemma 5.1, $Q^{\prime}$ contains
$v$ as $z\notin D[v]$. A contradiction. The lemma follows. ∎

##  6 Proof of Theorem 4.1

In this section we provide the proof of the following theorem. See 4.1 Here,
we do not assume that the underlying graph $G$ is planar. Let $n=|V(G)|$ and
$m=|E(G)|$. Wlog. assume $n\leq m$. Let $P=p_{1}p_{2}\dots p_{\ell}$ be the
directed path we consider. To answer our queries at hand for a failing vertex
$x\notin V(P)$, we use the same approach as in Lemma 3.6: observe that since
$x\notin V(P)$, by Fact 3.7, $u$ can reach $v$ through $P$ in $G-x$ if and
only if $first_{G-x}^{P}(u)\preceq_{P}last_{G-x}^{P}(v)$. In what follows we
only show how to compute $last_{G-x}^{P}(v)$ efficiently, since
$first_{G-x}^{P}(u)=last_{{G}^{\text{R}}-x}^{{P}^{\text{R}}}(u)$ and thus it
can be computed by proceeding identically on the reverse graph $G^{R}$. For
brevity, in the remaining part of this section we omit the
superscript/subscript $P$ and write $last_{G-x}$ instead $last_{G-x}^{P}$,
$last^{*}_{G}$ instead $last^{*P}_{G}$, $\prec$ instead of $\prec_{P}$, etc.

######  Definition 6.1.

We call a simple directed path $Q=e\to f$ of $G$ _satellite_ if it does not go
through $V(P)$ as intermediate vertices, i.e., $V(Q)\cap
V(P)\subseteq\\{e,f\\}$.

For any $v\in V\setminus V(P)$, we also denote by $last^{*}_{G-x}(v)$ the
latest vertex of $P$ that can reach $v$ in $G-x$ by a satellite path, if such
a vertex exists. For $v\in V(P)$, set $last^{*}_{G-x}(v)=v$. Having computed
$last^{*}_{G-x}(v)$, we then compute $last_{G-x}^{P}(v)$ using the following
lemma.

######  Lemma 6.2.

$last_{G-x}(v)$ is the latest vertex of $P$ in the SCC of $last^{*}_{G-x}(v)$
in $G-x$.

###### Proof.

Since $last^{*}_{G-x}(v)$ can reach $v$ in $G-x$, we have that
$last^{*}_{G-x}(v)\preceq last_{G-x}(v)$. As $x\notin V(P)$, there exists a
path $last^{*}_{G-x}(v)\to last_{G-x}(v)$ in $G-x$ following $P$.

If $v\in V(P)$, then, by the definition, $last_{G-x}(v)$ can reach
$v=last^{*}_{G-x}(v)$. Suppose $v\notin V(P)$ in $G-x$. Then take any simple
path $Q=last_{G-x}(v)\to v$ in $G-x$. Let $r$ be the last vertex on $Q$ such
that $r\in V(P)$. The subpath $r\to v$ of $Q$ is a satellite path, so
$r\preceq last^{*}_{G-x}(v)$ and thus there exists a $r\to last^{*}_{G-x}(v)$
path in $G-x$. Since $r$ is reachable from $last_{G-x}(v)$ in $G-x$, we
conclude that there exists a $last_{G-x}(v)\to last^{*}_{G-x}(v)$ path in
$G-x$. Hence, $last_{G-x}(v)$ and $last^{*}_{G-x}(v)$ are strongly connected
in $G-x$.

Clearly, all vertices that are strongly connected with $last^{*}_{G-x}(v)$ can
reach $v$ in $G-x$. Therefore, $last_{G-x}(v)$ is the latest vertex of $P$ in
the strongly connected component of $last^{*}_{G-x}(v)$ in $G-x$. ∎

Let us now note the following simple lemma on strong connectivity between
vertices of a path.

######  Lemma 6.3.

Let $H$ be a digraph and let $Q=q_{1},\ldots,q_{\ell}$ be a directed path in
$H$. Then for any $i=1,\ldots,\ell$, there exists two indices
$a\in\\{1,\ldots,\ell\\}$ and $b\in\\{i,\ldots,\ell\\}$ such that the only
vertices of $P$ that are strongly connected to $q_{i}$ are
$q_{a},\ldots,q_{b}$.

###### Proof.

Assume by contradiction that there exist $q_{j}$ and $q_{k}$ such that $q_{k}$
lies between $q_{i}$ and $q_{j}$ on $P$, and $q_{j}$ is strongly connected to
$q_{i}$, whereas $q_{k}$ is not strongly connected to $q_{i}$. Without loss of
generality suppose $i<j$ (the case $i>j$ is symmetric). We have $i<k<j$. Since
$q_{i}$ and $q_{j}$ are strongly connected, there exists a path $q_{j}\to
q_{i}$ in $G$. However, since $q_{k}$ lies before $q_{j}$ on $P$, there exists
a path $q_{k}\to q_{j}\to q_{i}$ in $G$. But $q_{i}$ lies before $q_{k}$ on
$P$, so there exists a $q_{i}\to q_{k}$ path in $G$. We conclude that $q_{i}$
and $q_{k}$ are strongly connected, a contradiction. ∎

Georgiadis et al. [32] showed the following theorem.

######  Theorem 6.4 ([32]).

Let $G$ be a digraph. In linear time one can construct a data structure
supporting $O(1)$-time queries of the form ’’are $u$ and $v$ strongly
connected in $G-x$?‘‘, where $u,v,x\in V(G)$.

Hence, after linear preprocessing, by Lemma 6.3 applied to $H=G$ and $Q=P$, we
could compute the vertex $last_{G-x}(v)$ (which, by Lemma 6.2, is the latest
vertex of $P$ in the SCC of $last^{*}_{G-x}(v)\in V(P)$) by using binary
search. Each step of binary search would take a single query to the data
structure of [32], so computing $last_{G-x}(v)$ out of $last^{*}_{G-x}(v)$
would take $O(\log{n})$ time.

However, we can do better using Theorem 4.4. In order to compute
$last_{G-x}(v)$ out of $last^{*}_{G-x}(v)$ in constant time using Theorem 4.4,
we assign a label $f(v)$ to each vertex $v$ as follows: for each vertex
$p_{i}\in V(P)$ we set $f(p_{i})=i$. For each vertex $w\notin V(P)$, we set
$f(w)=0$. The maximum labeled vertex in the SCC of $last^{*}_{G-x}(v)$ in
$G-x$ is precisely $last_{G-x}(v)$. Our final task is to show how to compute
$last^{*}_{G-x}(v)$ efficiently.

###  6.1 Computing $last^{*}_{G-x}(v)$.

For $i=\ell,\ldots,1$, define the _layer_ $L_{i}$ to be the vertices of
$V\setminus V(P)$ reachable from $p_{i}$ _by a satellite path_ , minus
$\bigcup_{j=i+1}^{\ell}L_{j}$. In other words, $L_{\ell}$ contains vertices
not on the path $P$ that are reachable from $p_{\ell}$ by a satellite path,
and each subsequent layer $L_{i}$ contains vertices reachable from $p_{i}$ by
a satellite path that are not reachable from $p_{i+1},\ldots,p_{\ell}$ by a
satellite path. The layers $L_{\ell},\ldots,L_{1}$ can be computed by
performing $\ell$ graph searches with starting points $p_{\ell},\dots,p_{1}$.
The graph search never enters the vertices of $P$ (except the starting vertex)
or the vertices of previous layers. This way, the total time needed to perform
all $\ell$ graph searches is linear.

For each layer $L_{i}$ we also compute the dominator tree $D_{i}$ of
$G[L_{i}\cup\\{p_{i}\\}]$ rooted at $p_{i}$. Denote by $d_{i}(w)$ the parent
of $w\in L_{i}$ in $D_{i}$. Since we have $E(G[L_{i}\cup\\{p_{i}\\}])\cap
E(G[L_{j}\cup\\{p_{j}\\}])=\emptyset$ for $i\not=j$, the dominator trees for
all $i=1,\dots,\ell$ can be computed in linear time overall.

Before proceeding with the computation, we need a few more definitions. Let
$v\in V\setminus V(P)$. We denote by $layer(w)$ the index in $j\in[\ell]$ for
which $w\in L_{j}$, if it exists. Recall that $last^{*}_{G}(v)$ is the latest
vertex on $P$ with a satellite path to $v$ in $G$.

Suppose $last^{*}_{G}(v)$ exists, since otherwise $last^{*}_{G-x}(v)$ does not
exist either. We distinguish two cases: (i) when $layer(x)$ does not exist or
$layer(x)\not=layer(v)$, and the more involved case (ii) when
$layer(x)=layer(v)$. We first show that case (i) is actually very easy to
handle.

######  Lemma 6.5.

If $layer(x)$ does not exist or $layer(x)\not=layer(v)$, then
$last^{*}_{G-x}(v)=last^{*}_{G}(v)$.

###### Proof.

Let $l_{v}=layer(v)$. By the definition of a layer,
$last^{*}_{G}(v)=p_{l_{v}}$. There is a satellite path from $p_{l_{v}}$ to $v$
in $G[L_{l_{v}}\cup\\{p_{l_{v}}\\}]$, avoiding $x$, as $x\notin L_{l_{v}}$.
Consequently, $last^{*}_{G}(v)\preceq last^{*}_{G-x}(v)$.

However, since $G-x$ is a strict subgraph of $G$, we also have
$last^{*}_{G-x}(v)\preceq last^{*}_{G}(v)$. We conclude that indeed
$last^{*}_{G-x}(v)=last^{*}_{G}(v)$. ∎

The most interesting case is when $layer(x)=layer(v)$, which we deal with as
follows. Set $l=layer(x)=layer(v)$. We will exploit the dominator tree
$D_{l}$. If $x$ does not dominate $v$ in $D_{l}$, then again one can show that
$last^{*}_{G-x}(v)=last^{*}_{G}(v)$. Otherwise, we will show that it is enough
to compute the latest vertex $p_{q}\in V(P)$, for which there is a path from
$p_{q}$ to some vertex of $D_{l}[x,v]$ in $G-x$. In order to efficiently
compute the appropriate vertices $p_{q}$, we in turn show that it is
sufficient to execute a precomputation phase during which we store for each
vertex $w\in V\setminus V(P)$ only the latest vertex $undom(w)\in V(P)$ such
that there is a satellite path from $undom(w)$ to $w$ avoiding the parent of
$w$ in $D_{layer(w)}$. Finally, we explain how to compute the values
$undom(w)$ for all $w$ in $O(m\log m/\log\log m)$ time. Below we study the
case $layer(x)=layer(v)$ in more detail.

######  Lemma 6.6.

If $layer(x)=layer(v)$ and $x$ is not an ancestor of $v$ in $D_{layer(v)}$,
then $last^{*}_{G-x}(v)=last^{*}_{G}(v)$.

###### Proof.

We already argued that $last^{*}_{G-x}(v)\preceq last^{*}_{G}(v)$. Since $x$
is not an ancestor of $v$ in $D_{l}$, the dominator tree of
$G[L_{l}\cup\\{p_{l}\\}]$, there is a path from $last^{*}_{G}(v)$ to $v$ in
$G[L_{l}\cup\\{p_{l}\\}]$, avoiding $x$. Hence,
$last^{*}_{G-x}(v)=last^{*}_{G}(v)$. ∎

Recall that we denote by $undom(w)$ the latest vertex on $P$ that has a
satellite path to $w$ in $G-d_{layer(w)}(w)$ (that is, avoiding the parent of
$w$ in the dominator tree $D_{layer(w)}$). In other words,
$undom(w)=last^{*}_{G-d_{layer(w)}(w)}(w)$. If no such vertex exists,
$undom(w)=\perp$.

######  Lemma 6.7.

Let $Q$ be a satellite path from $p_{k}=undom(w)$ to $w$ in $G$ avoiding
$d_{l}(w)$, where $l=layer(w)$. Then $k<l$ and $Q$ can be expressed as
$Q=Q_{1}Q_{2}Q_{3}$, such that $undom(w)\to y=Q_{1}\subseteq
G[L_{k}\cup\\{p_{k}\\}]$, $Q_{2}=yz\in V(L_{k})\times V(L_{l})$ (i.e., $Q_{2}$
is a single-edge path), and $z\to w=Q_{3}\subseteq
G[D_{l}[d_{l}(w)]\setminus\\{d_{l}(w)\\}]$.

###### Proof.

First observe that $k<l$ follows from the fact that $w$ is not reachable from
$p_{l+1},\ldots,p_{\ell}$ at all in the corresponding layers (by the
definition of $L_{l}$), and it is not reachable from $p_{l}$ in $G[L_{l}\cup
p_{l}]-d_{l}(w)$ by the definition of a dominator tree.

Moreover, by the definition of layers, there is no edge in $G$ from a vertex
of $L_{i}$ to a vertex of $L_{j}$, where $i>j$. In particular, there is no
edge from $L_{l}$ to $L_{k}$.

Since the edges in $G$ can only go from lower-numbered layers to the higher-
numbered ones, and $Q$ is a satellite path, $Q$ cannot visit a lower-numbered
layer after visiting a higher-numbered layer. Suppose that $Q$ goes through a
vertex of $a\in L_{j}$, where $k<j<l$. Let $R=a\to w$ be a subpath of $Q$. By
the definition of $Q$, $R$ does not go through $d_{l}(w)$. Moreover, $a$ is
reachable from $p_{j}$ in $G-d_{l}(w)$ (since $a\in L_{j}$ and $d_{l}(w)\in
L_{l}$) by a satellite path. Consequently, $w$ is reachable from $p_{j}$ in
$G-d_{l}(w)$ by a satellite path, which contradicts the fact that
$p_{k}=last^{*}_{G-d_{l}(w)}(w)$. We conclude that indeed $V(Q)\subseteq
L_{k}\cup\\{p_{k}\\}\cup L_{l}$, and the vertices of $L_{l}$ appear on $Q$
only after the vertices of $L_{k}$. Hence $Q$ can be expressed as
$Q_{1}(yz)Q_{3}$, where $Q_{1}\subseteq G[L_{k}\cup\\{p_{k}\\}]$ and
$Q_{3}\subseteq G[L_{l}]$.

It remains to prove that in fact we have $Q_{3}\subseteq
G[D_{l}[d_{l}(w)]\setminus\\{d_{l}(w)\\}]$. Clearly, $d_{l}(w)\notin V(Q_{3})$
since $Q$ avoids $d_{l}(w)$. Suppose a vertex $t\in
V(Q_{3})\cap(L_{l}\setminus D_{l}[d_{l}(w)])$ exists. Then, by Lemma 5.1 the
subpath $t\to w$ of $Q_{3}$ has to go through $d_{l}(w)$, a contradiction. ∎

For convenience we identify $\perp$ with $p_{0}$ and extend the order $\prec$
so that $\perp\prec p_{i}$ for all $i=1,\ldots,\ell$.

######  Lemma 6.8.

If $layer(x)=layer(v)$ and $x$ is an ancestor of $v$ in $D_{layer(v)}$, then
$last^{*}_{G-x}(v)=p_{q}$, where $q=\max\\{t:p_{t}=undom(w),w\in
D_{layer(v)}(x,v]\\}$.

###### Proof.

Let $l=layer(v)=layer(x)$. We first show that for all $w\in D_{l}(x,v]$, if
$undom(w)\neq\perp$ then the vertex $undom(w)$ has a satellite path to $v$
avoiding $x$ in $G$. By this, $p_{q}\preceq last^{*}_{G-x}(v)$ follows.
Consider a satellite path $Q$ from $undom(w)$ to $w$, avoiding $d_{l}(w)$. By
Lemma 6.7, $V(Q)\cap L_{l}\subseteq D_{l}[d_{l}(w)]\setminus\\{d_{l}(w)\\}$.
Since $D_{l}[d_{l}(w)]\setminus\\{d_{l}(w)\\}\subseteq
D_{l}[x]\setminus\\{x\\}$, $Q$ avoids $x$.

Now suppose that $p_{q}\prec last^{*}_{G-x}(v)$. Then, $undom(w)\prec
last^{*}_{G-x}(v)$ for all $w\in D_{l}(x,v]$. Take any simple satellite path
$Q$ from $last^{*}_{G-x}(v)$ to $v$ in $G-x$, and consider the earliest vertex
$w\in D_{l}(x,v]$ that it contains. Then the $last^{*}_{G-x}(v)\to w$ subpath
of $Q$ avoids all vertices on $D_{l}(x,w)$ (including $d_{l}(w)$). This
contradicts that $undom(w)$ is the latest vertex on $P$ that has a satellite
path to $w$ in $G-d_{l}(w)$. Hence, $last^{*}_{G-x}(v)\preceq p_{q}$ and we
obtain $last^{*}_{G-x}(v)=p_{q}$. ∎

Suppose we have the vertices $undom(w)$ computed for all $w\in V\setminus
V(P)$. For any $i=1,\ldots,\ell$, let $D_{i}^{\prime}$ be the tree $D_{i}$
with labels on its edges added, such that the label of an edge $d_{i}(w)w$,
where $w\in L_{i}$, is equal to $undom(w)$. Then, by Lemma 6.8, computing
$last^{*}_{G-x}(v)$ when $l=layer(x)=layer(v)$ and $x$ is an ancestor of $v$
in $D_{l}$ can be reduced to finding a maximum label on the $x^{\prime}$ to
$v$ path of $D_{l}^{\prime}$, where $x^{\prime}$ is the child of $x$ in
$D_{l}$ that $v\in D_{l}[x^{\prime}]$. Such queries can be answered in
constant time after linear preprocessing of $D_{l}^{\prime}$: we can use the
data structure of [12] for finding $x^{\prime}$, and the data structure of
[21] for finding the maximum label on a path.

###  6.2 Computing $undom(w)$, for all $w$, in $O(n\log n/\log\log n)$ time.

Our final task is to compute the vertices $undom(w)$ for all $w\in V\setminus
V(P)$. Let initially $ud(w):=\perp$ for all $w\in V\setminus V(P)$. The goal
is to eventually obtain $ud(w)=undom(w)$ for each $w$. The computation will be
divided into $\ell$ phases numbered $\ell$ down to $1$. During the phase $i$,
we process all edges $xy\in(V\times L_{i})\cap E(G)$. Recall that by the
definition of the levels, there is no edge $e\in V(L_{j})\times V(L_{i})$ for
$j>i$.

Each phase is subdivided into rounds, where each round processes a single edge
from $E(G)\cap((V\setminus L_{i})\times L_{i})$ and some edges from
$E(G)\cap(L_{i}\times L_{i})$. The edges originating in ’’later‘‘ layers are
processed before the edges originating in ’’earlier‘‘ layers. Consider the
round processing an edge $xy\in L_{j}\times L_{i}$, where $j<i$. We start by
initializing a queue of edges $Q$, initially containing only $xy$. While $Q$
is not empty, we extract an edge $zw$ from $Q$. We test whether
$ud(w)\not=\perp$, and if so, we set $ud(w):=p_{j}$, we remove from $G$ all
edges from $E(G)\cap(D_{i}[w]\times(L_{i}\setminus D_{i}[w]))$ and push them
to $Q$. The round ends when $Q$ becomes empty. Afterwards, we proceed with the
next round. A phase ends when there are no unprocessed edges incident to a
vertex of $L_{i}$.

We now prove the correctness of the above procedure.

######  Lemma 6.9.

Fix some phase $i$. After all rounds processing edges from

$E(G)\cap((L_{j}\cup L_{j+1}\cup\ldots L_{i-1})\times L_{i}),$

we have $ud(w)=undom(w)$ for all $w\in L_{i}$ such that $p_{j}\preceq
undom(w)$ and $ud(w)=\perp$ for all $w\in L_{i}$ such that $undom(w)\prec
p_{j}$.

###### Proof.

We proceed by induction on $j$. The base case is $j=i$ and then the claim is
clearly true.

Suppose $j<i$ and that the claim holds for all $j^{\prime}>j$. Since edges
$xy\in E(G)\cap(L_{j}\times L_{i})$ are processed always after
$E(G)\cap((L_{j+1}\cup\ldots L_{i-1})\times L_{i})$, and the procedure can
only set $ud(w):=j$ if $ud(w)=\perp$ when processing such an $xy$, we need to
prove that for all $w\in L_{i}$:

  1. (1)

if the procedure sets $ud(w)=p_{j}$ then there exists a satellite $p_{j}\to w$
path avoiding $d_{i}(w)$, and

  2. (2)

if $ud(w)=\perp$ before processing edges originating in $L_{j}$ and there is a
satellite $p_{j}\to w$ path avoiding $d_{i}(w)$, then the procedure will set
$ud(w)=p_{j}$.

Let us start with proving (1). We prove this by induction on the edges
extracted from the queue $Q$, during the round for which we set $ud(w)=p_{j}$.
The base case is when the first edge gets extracted from $Q$, that is, the
edge $xy\in E(G)\cap(L_{j}\times L_{i})$ that initiates the round. In this
case, there is a path from $p_{j}$ to $x$ in $L_{j}$ (which avoids $d_{i}(w)$
as $d_{i}(w)\notin L_{j}$) followed by the edge $xy$. Hence the claim holds
for the base case. Now suppose the claim holds for all edges that have been
extracted from $Q$ prior to some edge $zw$ in this round. Consider the moment
when $zw$ was inserted into $Q$; it was while another edge
$e^{\prime}=z^{\prime}w^{\prime}$ was being processed, we correctly set
$ud(w^{\prime})=p_{j}$ (by induction), and $zw$ was an edge from
$E(G)\cap(D_{i}[w^{\prime}]\times(L_{i}\setminus D_{i}[w^{\prime}])$.
Moreover, by Lemma 5.2, $d_{i}(w)$ is an ancestor of $z$ in $D_{i}$. Since
$w\notin D_{i}[w^{\prime}]$, $d_{i}(w)$ is also ancestor of $w^{\prime}$ in
$D_{i}$, as $w^{\prime}$ is an ancestor of $z$. Overall, we have a path from
$p_{j}$ to $w^{\prime}$ avoiding $d_{i}(w^{\prime})$, and all ancestors of
$d_{i}(w^{\prime})$ in $D_{i}$ (as otherwise, by Lemma 5.1, this $p_{j}\to
w^{\prime}$ path would go through $d_{i}(w^{\prime})$, which would be a
contradiction), in particular $d_{i}(w)$. By Lemma 5.3, $w^{\prime}$ has a
path to $z$ avoiding all vertices from $V\setminus D_{i}[w^{\prime}]$
(including $d_{i}(w)$). Hence, combined with edge $zw$, there is a path from
$p_{j}$ to $w$ avoiding $d_{i}(w)$. This concludes the first part of the
proof.

Now let us consider item (2). For a contradiction, suppose there exists such
$w\in L_{i}$ that $ud(w)=\perp$ before processing the edges originating in
$L_{j}$, and there exists a simple satellite path $Q=p_{j}\to w$ avoiding
$d_{i}(w)$, but the procedure does not set $ud(w):=p_{j}$. By the inductive
hypothesis, $undom(w)=p_{j}$. Hence, by Lemma 6.7, $Q$ first goes through the
layer $L_{j}$, then through a single edge in $xy\in L_{j}\times L_{i}$, and
then through the layer $L_{i}$. Out of such vertices $w$ and paths $Q$, choose
such $w$ and $Q$ so that the round when $xy$ is processed is earliest possible
and, in case of ties, $Q$ has the minimal number of edges in $L_{i}\times
L_{i}$ that are not of the form $d_{i}(a)a$ (i.e., do not go from a parent to
a child in $D_{i}$). Let $Q=Q_{1}(xy)Q_{3}$. Let all the edges not of the form
$d_{i}(a)a$ in $Q_{3}$ be $x_{1}y_{1},\ldots,x_{g}y_{g}$ in order of their
appearance on $Q_{3}$. We possibly have $g=0$. Set $y_{0}=y$.

We first show that for all $k=1,\ldots,g$, $d_{i}(y_{k})$ is a proper ancestor
of $y_{k-1}$ in $D_{i}$. Suppose $d_{i}(y_{k})$ is not a proper ancestor of
$y_{k-1}$. Since by Lemma 5.2 $d_{i}(y_{k})$ is an ancestor of $x_{k}$, and
all the edges in the subpath $y_{k-1}\to x_{k}$ go to children in the
dominator tree, $d_{i}(y_{k})\in D_{i}[y_{k-1}]$. Hence, the subpath
$y_{k-1}\to y_{k}$ of $Q$ could be replaced with a $y_{k-1}\to y_{k}$ path
that goes only to the children in the dominator tree, contradicting the
minimality of $g$. Similarly we can show that $y_{k}\neq y_{k-1}$ for all
$k=1,\ldots,g$.

It follows that $d_{i}(y_{k})$ is an ancestor of $d_{i}(y_{k-1})$ and also
that each subpath $y\to y_{k}$ goes only through vertices of
$D_{i}[d_{i}(y_{k})]\setminus\\{d_{i}(y_{k})\\}$. In particular, for each
$y_{k}$, the subpath $p_{j}\to y_{k}$ avoids $d_{i}(y_{k})$. Observe that we
also necessarily have $y_{g}=w$, as otherwise, $w$ would be a proper
descendant of $y_{g}$, and thus the subpath $y_{g}\to w$ would go through
$d_{i}(w)$.

Suppose that for some $k\in\\{0,\ldots,g-1\\}$ we have $undom(y_{k})\neq
p_{j}$. Then, since a satellite path $p_{j}\to y_{k}$ avoiding $d_{i}(y_{k})$
exists, $p_{j}\prec undom(y_{k})=p_{j^{\prime}}$. Let $R$ be a
$p_{j^{\prime}}\to y_{k}$ satellite path avoiding $d_{i}(y_{k})$. By Lemma
6.7, all the vertices of $L_{i}$ that $R$ goes through lie in
$D_{i}[d_{i}(y_{k})]\setminus\\{d_{i}(y_{k})\\}$. Consequently, $R$ avoids
$d_{i}(w)$ since $d_{i}(w)=d_{i}(y_{g})$ is an ancestor of $d_{i}(y_{k})$. So,
by replacing in $Q$ the $p_{i}\to y_{k}$ subpath with $R$ we would obtain a
$p_{j}^{\prime}\to w$ satellite path avoiding $d_{i}(w)$, which would
contradict $undom(w)=p_{j}$.

By the fact that $xy$ is the earliest possible processed edge and the
minimality of $g$, it follows that for all $y_{k}=y_{0},\ldots,y_{g-1}$ the
algorithm sets $ud(y_{k})=p_{j}$. In particular, after the algorithm sets
$ud(y_{g-1}):=p_{j}$, for all remaining edges $x^{\prime}y^{\prime}\in
L_{i}\times(L_{i}\setminus D_{i}[y_{g-1}])$, such that $ud(y^{\prime})=\perp$,
$ud(y^{\prime}):=p_{j}$ is set. Note that by the fact that $d_{i}(y_{g})$ is a
proper ancestor of $y_{g-1}$ and $y_{g}\neq y_{g-1}$, it follows that
$x_{g}y_{g}\in L_{i}\times(L_{i}\setminus D_{i}[y_{g-1}])$. If
$x_{g}y_{g}\notin E(G)$ at this point, then $ud(w=y_{g})$ has already been set
to something else than $\perp$ – a contradiction. Otherwise, $x_{g}y_{g}$ will
be processed at this point and therefore $ud(w=y_{g})$ will be set to $p_{j}$,
a contradiction. ∎

######  Corollary 6.10.

After the algorithm finishes, we have $ud(w)=undom(w)$ for all $w\in
V\setminus V(P)$.

###### Proof.

We apply Lemma 6.9 for all $i$ and $j=1$. ∎

Finally, we now analyze the time complexity of the procedure that computes the
vertices $undom(w)$ for all $w\in V\setminus V(P)$.

######  Lemma 6.11.

The algorithm from this section can be implemented to run in time
$O\left(m\frac{\log m}{\log\log m}\right)$.

###### Proof.

The time for computing the dominator trees of all layers $L_{i}$ is $O(m)$ in
total. Moreover, we can compute the correct order with which to process the
incoming edges of each layer $L_{i}$, in $O(n+m)$ in total using radix-sort.
Observe that the insertions and extraction to/from the maintained queue $Q$,
through all layers $L_{i}$, take $O(m)$ time overall since each edge is
inserted into $Q$ at most once.

Now we bound the total time spent on reporting and deleting the edges from
$G$. This can be done with the help of a dynamic two-dimensional range
reporting data structure, as we next explain. We build such a data structure
for each graph $G[L_{i}]$ separately – recall that in the $i$-th phase we only
report/remove the edges of $E(G)\cap(L_{i}\times L_{i})=E(G[L_{i}])$.

Let $n^{\prime}=|L_{i}|$ and $m^{\prime}=|E(G[L_{i}])|$. Let
$ord:L_{i}\cup\\{p_{i}\\}\to[1..n^{\prime}+1]$ be some preorder of the
dominator tree $D_{i}$. Let $size(v)=|V(D_{i}[v])|$. Clearly, both $ord$ and
$size$ can be computed in linear time. Note that we have $u\in D_{i}[v]$ if
and only if $ord(u)\in[ord(v),ord(v)+size(v)-1]$.

We map each edge $xy\in E(G[L_{i}])$ to a point $(ord(x),ord(y))$ on the
plane. Let $A$ be the set of obtained points. We store the points $A$ in a
two-dimensional dynamic range reporting data structure of Chan and Tsakalidis
[16].666In our application, any _decremental_ two-dimensional range reporting
data structure would be enough to obtain a nearly linear time algorithm. In
fact, what we need is a range _extraction_ data structure that removes all the
reported points that remain in the query rectangle so that no point is
reported twice. To the best of our knowledge, such a problem is not well-
studied and this is why we use a seemingly much more general data structure of
[16]. This data structure supports insertions and deletions in
$O(\log^{2/3+o(1)}{b})$ time, and allows reporting all points in a query
rectangle in $O\left(\frac{\log{b}}{\log\log{b}}+k\right)$ time, where $k$ is
the number of points reported and $b$ is the maximum number of points present
in the point set at any time. Hence, we can build the range reporting data
structure in
$O(m^{\prime}\log^{2/3+o(1)}{m^{\prime}})=O\left(m^{\prime}\frac{\log{m^{\prime}}}{\log\log{m^{\prime}}}\right)$
time, by inserting all points from $A$.

Suppose we are required to remove and report the edges of
$E(G[L_{i}])\cap(D_{i}[v]\times(L_{i}\setminus D_{i}[v]))$. Then, it is easy
to see that this can be done by querying the range reporting data structure
for the edges corresponding to points in the set

$[ord(u),ord(u)+size(u)-1]\times([1,ord(u)-1]\cup[ord(u)+size(u),n^{\prime}]),$

which, clearly, consists of two orthogonal rectangles in the plane. This way,
we get all the remaining edges $xy$ of $G[L_{i}]$ such that $x\in D[v]$ and
$y\notin D[v]$. Subsequently, (the corresponding points of) all the found
edges are removed from the range reporting data structure. Since each edge of
$G[L_{i}]$ is reported and removed only once, and we issue $O(m^{\prime})$
queries to the range reporting data structure, the total time used to process
any sequence of deletions is
$O\left(m^{\prime}\frac{\log{m^{\prime}}}{\log\log{m^{\prime}}}\right)$. Since
the sum of $m^{\prime}$ over all layers is $m$, the total time to report all
edges and removing them at all levels $L_{i}$ is
$O\left(m\frac{\log{m}}{\log\log{m}}\right)$. ∎

##  7 Proof of Theorem 4.3

In this section we prove the following theorem. See 4.3 Let the subsequent
vertices of $P$ be $p_{1},\ldots,p_{\ell}$, i.e., $P=p_{1}\ldots p_{\ell}$.
For simplicity, let us set $\prec:=\prec_{P}$. Recall that the failed vertex
$x$ satisfies $x\in V(P)$.

Define $G_{1}$ and $G_{2}$ to be the two subgraphs of $G$ lying weakly on the
two sides of $P$. More formally, the bounding cycle of the infinite face
(which, by our assumption, contains $p_{1}$ and $p_{\ell}$) of $G$ can be
expressed as $C_{1}C_{2}$, where $C_{1}$ is a non-oriented $p_{1}\to p_{\ell}$
path, and $C_{2}$ is a non-oriented $p_{\ell}\to p_{1}$ path. Then we define
$G_{1}$ to be the subgraph of $G$ weakly inside the cycle $C_{1}P^{R}$ (where
$P^{R}$ is the non-oriented path $P$ reversed), and $G_{2}$ to be the subgraph
of $G$ weakly inside the cycle $C_{2}P$. We have $G_{1}\cap G_{2}=P$. Note
that $P$ is a part of the infinite face‘s bounding cycle of each $G_{i}$.

Our strategy for finding a $u\to v$ path $Q$ in $G-x$, $x\in V(P)$ that goes
through $V(P)$ will be to consider a few cases based on how $Q$ crosses $P$.
In order to minimize the number of cases we will define a number of auxiliary
notions in Section 7.1. Next, in Section 7.2 we will show how these notions
can be efficiently computed. Subsequently in Section 7.3 we will show a few
technical lemmas stating that we only need to look for paths $Q$ of a very
special structure. Finally, in Section 7.4 we describe the query procedure.

###  7.1 Auxiliary notions

We first extend the notation $first,last,first^{*},last^{*}$ from Section 6 to
subpaths of $P$. For any $H\subseteq G$ denote by $first_{H}(v,a,b)$
($last_{H}(v,a,b)$) the earliest (latest resp.) vertex of $P[a,b]$ that $v$
can reach (that can reach $v$, resp.) in $H$. In fact, as we will see, we will
only need to compute $first_{H}(v,a,b)$ or $last_{H}(v,a,b)$ for $v\in
V(P[a,b])$.

Similarly, for $v\in V\setminus V(P)$ denote by $first^{*}_{H}(v,a,b)$
($last^{*}_{H}(v,a,b)$) the earliest (latest resp.) vertex of $P[a,b]$ that
$v$ can reach (that can reach $v$, resp.) _by a satellite path_ in $H$. For
$v\in V(P)$ we set $first^{*}_{H}(v,a,b)=last^{*}_{H}(v,a,b)=v$ if $a\preceq
v\preceq b$. Note that in some cases we leave the values
$first^{*}_{H}(v,a,b)$ and $last^{*}_{H}(v,a,b)$ undefined.

For brevity we sometimes omit the endpoints of the subpath if we care about
some earliest/latest vertices of the whole path $P=P[p_{1},p_{\ell}]$, and
write (as in Section 6) e.g., $first^{*}_{H}(v)$ instead of
$first^{*}_{H}(v,p_{1},p_{\ell})$ or $last_{H}(v)$ instead of
$last_{H}(v,p_{1},p_{\ell})$.

We will also need the notions of earliest/latest jumps and detours that are
new to this section.

######  Definition 7.1.

Let $w\in V(P)$. Let $H$ be a digraph such that $V(P)\subseteq V(H)$. We call
the earliest vertex of $P$ that $w$ can reach using a satellite path in $H$
the _earliest jump_ of $w$ in $H$ and denote this vertex by
$\alpha^{-}_{H}(w)$. Similarly, we call the latest vertex of $P$ that $w$ can
reach using a satellite path in $H$ the _latest jump_ of $w$ in $H$ and denote
this vertex by $\alpha^{+}_{H}(w)$.

######  Definition 7.2.

Let $x=p_{k}$. We define a _detour_ of $x$ to be any directed satellite path
$D=p_{i}\to p_{j}$, where $i<k<j$. Detour $D$ is called _minimal_ if there is
no detour $D^{\prime}=p_{i^{\prime}}\to p_{j^{\prime}}$ of $x$ such that
$i\leq i^{\prime}\leq j^{\prime}\leq j$ and $j^{\prime}-i^{\prime}<j-i$. A
pair $(p_{i},p_{j})$ is called a _minimal detour pair_ of $x$ if there exists
a minimal detour of $x$ of the form $p_{i}\to p_{j}$.

The fact that $p_{1}$ and $p_{\ell}$ lie on a single face of $G$ implies the
following important property of minimal detours.

######  Lemma 7.3.

For any $x\in V(P)$, there exist at most two minimal detour pairs of $x$.

###### Proof.

Let $x=p_{k}$. Assume the contrary and suppose there are at least three
minimal detour pairs and let us take some three minimal detours
$D_{1},D_{2},D_{3}$ corresponding to these pairs. Some two of
$D_{1},D_{2},D_{3}$, say $D_{1},D_{2}$ are both contained in some of $G_{1}$
and $G_{2}$ – say $G_{1}$.

Suppose $D_{1}=p_{i}\to p_{j}$ and $D_{2}=p_{i^{\prime}}\to p_{j^{\prime}}$.
Assume w.l.o.g. that $i\leq i^{\prime}$. Then since $(p_{i},p_{j})$ and
$(p_{i^{\prime}},p_{j^{\prime}})$ are distinct minimal detour pairs of $x$, we
have $i<i^{\prime}<k<j<j^{\prime}$.

Recall that all vertices of $P$ lie on the infinite face of $G_{1}$. Since
$i<i^{\prime}<j<j^{\prime}$, any $p_{i}\to p_{j}$ path in $G_{1}$ crosses
(i.e., has a common internal vertex with) any $p_{i^{\prime}}\to
p_{j^{\prime}}$ path in $G_{1}$. Let $z\in(V(D_{1})\cap V(D_{2}))\setminus
V(P)$. So $D_{1}$ can be represented as $D_{1}^{\prime}D_{1}^{\prime\prime}$,
where $D_{1}^{\prime\prime}=z\to p_{j}$. Similarly,
$D_{2}=D_{2}^{\prime}D_{2}^{\prime\prime}$, where
$D_{2}^{\prime}=p_{i^{\prime}}\to z$. Observe that
$D_{2}^{\prime}D_{1}^{\prime\prime}=p_{i^{\prime}}\to p_{j}$ is a detour of
$x$. But since $j-i^{\prime}<j-i$, this contradicts the minimality of $D_{1}$.
∎

###  7.2 Computing $first,last,first^{*},last^{*}$, jumps and detours

######  Lemma 7.4.

After linear preprocessing of $G$, for any $v\in V$ and $a,b\in V(P)$, where
$a\preceq b$, the vertices $first^{*}_{G}(v,a,b)$ and $last^{*}_{G}(v,a,b)$
(if they exist) can be computed in $O(\log{n})$ time.

###### Proof.

The case $v\in V(P)$ is trivial by the definition of $first^{*}_{G}(v,a,b)$
and $last^{*}_{G}(v,a,b)$: these vertices are defined and equal to $v$ only
for $a\preceq v\preceq b$. Hence, below we assume $v\in V\setminus V(P)$.

First observe that any satellite path is entirely contained in either $G_{1}$
or $G_{2}$. Hence, $first^{*}_{G}(v,a,b)$ is the earlier of
$first^{*}_{G_{1}}(v,a,b)$ and $first^{*}_{G_{2}}(v,a,b)$. In the following we
focus on computing $first^{*}_{G_{1}}(v,a,b)$. Satellite paths in $G_{2}$ can
be handled identically. Computing latest vertices can be done symmetrically.

Note that since $v\notin V(P)$, a satellite path $Q=v\to V(P[a,b])$ in $G_{1}$
does not use the outgoing edges of the vertices of $P$. Let us thus remove the
outgoing edges of all $w\in V(P)$ from $G_{1}$ and this way obtain
$G_{1}^{\prime}$. Note that all the remaining paths in $G_{1}^{\prime}$ are
satellite now and all the satellite paths from $v$ in $G_{1}$ are preserved in
$G_{1}^{\prime}$.

For simplicity let us assume that $\ell$ is a power of 2. This is without loss
of generality, since otherwise we could extend $P$ by adding less than $\ell$
vertices ’’inside‘‘ the last edge of $P$ so that the length of $P$ becomes a
power of two. Recall that all the outgoing edges of $V(P)$ are removed in
$G_{1}^{\prime}$ anyway so this extension does not influence reachability or
the answers to the considered queries.

Let $\mathcal{I}$ be the set of _elementary_ intervals defined as follows: for
each $f\in\\{0,\ldots,\log\ell\\}$ the intervals $[(k-1)\cdot 2^{f}+1,k\cdot
2^{f}]$, for all $k\in[\frac{\ell}{2^{f}}]$, is included in $\mathcal{I}$.
Observe that $\mathcal{I}$ has $\ell-1$ intervals and these intervals can be
conveniently arranged into a full binary tree.

We further extend $G_{1}^{\prime}$ by adding an auxiliary vertex $p_{[e,f]}$
for each $[e,f]\in\mathcal{I}$ such that $e<f$. We also identify each vertex
$p_{i}\in V(P)$ with $p_{[i,i]}$. For each $[e,f]\in\mathcal{I}$ with $e<f$ we
add to $G_{1}^{\prime}$ two edges $p_{[e,m]}p_{[e,f]}$ and
$p_{[m+1,f]}p_{[e,f]}$, where $m=\left\lfloor\frac{e+f}{2}\right\rfloor$.

Observe that for any $[e,f]\in\mathcal{I}$, and $v\in V\setminus V(P)$ a path
from $v$ to any of $p_{e},\ldots,p_{f}$ exists in $G_{1}^{\prime}$ if and only
if a $v\to p_{[e,f}]$ path exists in $G_{1}^{\prime}$.

Since the vertices $p_{1},\ldots,p_{\ell}$ lie on a single face of $G_{1}$ in
this order, after the extension the graph $G_{1}^{\prime}$ remains planar (see
Figure 1). We can thus build a reachability oracle of Holm et al. [35] for
$G_{1}^{\prime}$ in linear time so that we can answer reachability queries in
$G_{1}^{\prime}$ in constant time.

$p_{1}$$p_{\ell}$$p_{[1,2]}$$p_{[3,4]}$$p_{[5,6]}$$p_{[7,8]}$$p_{[9,10]}$$p_{[11,12]}$$p_{[13,14]}$$p_{[15,16]}$$p_{[1,4]}$$p_{[5,8]}$$p_{[9,12]}$$p_{[13,16]}$$p_{[1,8]}$$p_{[9,16]}$$p_{[1,16]}$$G_{1}^{\prime}$
Figure 1: Auxiliary vertices corresponding to elementary intervals.

Note that we would be able to compute $first^{*}_{G_{1}}(v,a,b)$ in
$O(\log{(b-a+1)})$ time via binary search if only we could query in $O(1)$
whether a path from either of $p_{x},\ldots,p_{y}$ to $v$ exists for an
arbitrary interval $[x,y]$. However, in $O(1)$ time we can only handle such
queries for $[x,y]\in\mathcal{I}$. It is well-known that one can decompose an
arbitrary $[x,y]$ into $O(\log{n})$ elementary intervals: this way, we could
implement a single step of binary search in $O(\log{n})$ time and thus
computing $first^{*}_{G_{1}}(v,a,b)$ would take $O(\log^{2}{n})$ time.

In order to compute $first^{*}_{G_{1}}(v,a,b)$ faster, we use a slightly more
complicated binary-search-like recursive procedure as follows. The recursive
procedure first is passed a single parameter $[e,f]\in\mathcal{I}$ and returns
the earliest vertex from $p_{\max(a,e)},\ldots,p_{\min(b,f)}$ reachable from
$v$ in $G_{1}^{\prime}$, or nil if such a vertex does not exits. This way, in
order to find $first^{*}_{G_{1}}(v,a,b)$ we compute
$\texttt{first}([1,\ell])$.

The procedure $\texttt{first}([e,f])$ is implemented as follows.

  1. 1.

If $[a,b]\cap[e,f]=\emptyset$ then we return nil.

  2. 2.

Otherwise, if $[e,f]\subseteq[a,b]$ and there is no $v\to p_{[e,f]}$ path in
$G_{1}^{\prime}$ (which can be decided in $O(1)$ time with a single
reachability query on $G_{1}^{\prime}$), we also return nil.

  3. 3.

Otherwise if $e=f$ we return $p_{e}$.

  4. 4.

Finally, if none of the above cases apply, let
$m=\left\lfloor\frac{e+f}{2}\right\rfloor$. If $\texttt{first}([e,m])=v$, we
return $v$. Otherwise (i.e., if $\texttt{first}([e,m])$ returned nil), we
compute and return $\texttt{first}([m+1,f])$.

It is easy to see that the procedure is correct. Let us now analyze its
running time. We say that a call to $\texttt{first}([e,f])$ is _non-leaf_ if
it invokes the procedure recursively. Note that the query algorithm runs in
time linear in the number of non-leaf calls $\texttt{first}([e,f])$. We now
show that the number of non-leaf calls is $O(\log{n})$.

First observe that for each non-leaf call we have
$[e,f]\cap[a,b]\neq\emptyset$. Let us first count non-leaf calls such that
$[e,f]\not\subseteq[a,b]$. Suppose for some $k$ there are at least 3 such
(pairwise disjoint) intervals $[e_{i},f_{i}]$, for $i=1,2,3$ with
$f_{i}-e_{i}+1=2^{k}$. Let $e_{1}<e_{2}<e_{3}$. Since $[a,b]$ intersects both
$[e_{1},f_{1}]$ and $[e_{2},f_{2}]$ but does not contain any of them
$e_{2}\in[a,b]$. Similarly, since $[a,b]$ intersects both $[e_{2},f_{2}]$ and
$[e_{3},f_{3}]$ but does not contain any of them $f_{2}\in[a,b]$. Hence,
$[e_{2},f_{2}]\subseteq[a,b]$, a contradiction. So there are at most 2 such
intervals per $k\in\\{0,\ldots,\log_{2}\ell\\}$, and conclude that there are
$O(\log{n})$ non-leaf calls such that $[e,f]\not\subseteq[a,b]$.

Now suppose $\texttt{first}([e,f])$ is a non-leaf call and
$[e,f]\subseteq[a,b]$. Since this is a non-leaf call, there is a path from $v$
to some of $p_{j}$, where $j\in[e,f]$ in $G_{1}^{\prime}$, and the call will
return $p_{j}$. Consequently, the root call will also return $p_{j}$. We
conclude that all such non-leaf calls return the same $p_{j}$. But there are
only $O(\log{n})$ intervals $[e,f]$ such that $p_{j}\in[e,f]$. ∎

######  Lemma 7.5.

After linear preprocessing, we can compute $first_{G-x}(v,a,b)$
($last_{G-x}(v,a,b)$) for all $v,a,b,x\in V(P)$ such that $a\preceq v\preceq
b\prec x$ or $x\prec a\preceq v\preceq b$ in $O(\log{n})$ time.

###### Proof.

We build the data structure of Theorem 6.4 for graph $G$ in linear time. We
only show how to compute $first_{G-x}(v,a,b)$, as $last_{G-x}(v,a,b)$ can be
computed completely analogously.

Let $v^{\prime}=first_{G-x}(v,a,b)$. Observe that $v^{\prime}\preceq v$ since
a path $v\to v$ exists in $G-x$. Note that $P[a,b]$ is a path in $G-x$. Since
a path $v^{\prime}\to v$ exists in $G-x$ (since $P[v^{\prime},v]$ is a subpath
of $P[a,b]$), $v$ and $v^{\prime}$ are in fact strongly connected in $G-x$.

By Lemma 6.3, if $v^{\prime}$ is strongly connected to $v$ in $G-x$, then all
$y\in V(P)$, $v^{\prime}\preceq y\preceq v$, are also strongly connected to
$v$ in $G-x$. Consequently, we can find $v^{\prime}$ by binary searching on
the subpath $P[a,v]$ for the last vertex not strongly connected to $y$ in
$G-x$. A single step of binary search is executed in $O(1)$ time by Theorem
6.4. ∎

######  Lemma 7.6.

For a digraph $H$ such that $V(P)\subseteq V(H)$, the earliest and latest
jumps of all $w\in V(P)$ can be computed in linear time.

###### Proof.

We only show how to compute earliest jumps, as latest jump can be computed
analogously.

We first replace each $p_{i}\in V(P)$ in $H$ with two vertices
$p_{i}^{\text{in}}$ and $p_{i}^{\text{out}}$. Next we change each original
edge $p_{i}v$ of $H$ into $p_{i}^{\text{out}}v$, and subsequently turn each
edge $up_{i}$ of $H$ into $up_{i}^{\text{in}}$. Observe that every
$p_{i}^{\text{out}}$ has only outgoing edges, whereas every
$p_{i}^{\text{in}}$ has only incoming edges.

Observe that there is a 1-1 correspondence between $p_{i}^{\text{out}}\to
p_{j}^{\text{in}}$ paths in $H$ and $p_{i}\to p_{j}$ _satellite_ paths in $H$
before the transformation since no path in the current $H$ can go through
either $p_{l}^{\text{in}}$ or $p_{l}^{\text{out}}$ as an intermediate vertex.
Therefore, the task of computing the earliest jumps can be reduced to
computing, for each $i\in[1,\ell]$, the minimum $j$ such that
$p_{j}^{\text{in}}$ is reachable from $p_{i}^{\text{out}}$ in the transformed
$H$. This, in turn, can be done as follows, in an essentially the same way as
we computed the layers in Section 6.1.

For each $i=1,\ldots,\ell$, we run a reverse graph search from
$p_{i}^{\text{in}}$ in $H$ that only enters vertices that have not been
visited so far. If $w\in V(H)$ gets visited in phase $i$, we set
$\alpha_{H}^{-}(w)=i$. Observe that if a vertex $w$ is visited in phase $i$,
this means that there exists a path $w\to p_{i}^{\text{in}}$ in $H$ and for
any $j<i$ there is no path $w\to p_{j}^{\text{in}}$ in $H$. This in particular
applies to vertices $w$ of the form $p_{l}^{\text{out}}$.

Finally, observe that the reverse graph search takes linear total time through
all phases. ∎

######  Lemma 7.7.

The minimal detour pairs of all $x\in V(P)$ can be computed in linear time.

###### Proof.

From the proof of Lemma 7.3 it follows that in fact there is at most one
minimal detour pair for each $x\in V(P)$ in each $G_{i}$, $i=1,2$. We thus
compute this pair (if it exists) separately for $G_{1}$ and $G_{2}$. In the
following we focus on $G_{1}$ since $G_{2}$ can be handled identically.

Let $x=p_{k}$. Suppose a minimal detour pair $(p_{i},p_{j})$ of $x$ in $G_{1}$
exists. Then the latest jump of $p_{i}$ in $G_{1}$ also exists and $x\prec
p_{j}\preceq\alpha^{+}_{G_{1}}(p_{i})$. Let $a\in V(P)$ be the latest vertex
$a\prec x$ such that $x\prec\alpha^{+}_{G_{1}}(a)$. We conclude that
$p_{i}\preceq a$. Similarly, the earliest (with respect to the original order
of $P$) jump of $p_{j}$ in ${G_{1}}^{\text{R}}$ also exists and
$\alpha^{-}_{{G_{1}}^{\text{R}}}(p_{j})\preceq p_{i}\prec x$. Let $b\in V(P)$
be the earliest vertex satisfying $x\prec b$ such that
$\alpha^{-}_{{G_{1}}^{\text{R}}}(b)\prec x$. Observe that we have $b\preceq
p_{j}$, and thus $p_{i}\preceq a\prec x\prec b\preceq p_{j}$.

We now prove that in fact $p_{i}=a$ and $p_{j}=b$. First observe that since
there exist detours $D_{b}=\alpha^{-}_{{G_{1}}^{\text{R}}}(b)\to b$ and
$D_{a}=a\to\alpha^{+}_{G_{1}}(a)$ of $x$ in $G_{1}$, by the definition of $a$
we have $\alpha^{-}_{{G_{1}}^{\text{R}}}(b)\preceq a$ and
$b\preceq\alpha^{+}_{G_{1}}(a)$. So,
$\alpha^{-}_{{G_{1}}^{\text{R}}}(b)\preceq a\prec x\prec
b\preceq\alpha^{+}_{G_{1}}(a)$. But
$\alpha^{-}_{{G_{1}}^{\text{R}}}(b),a,b,\alpha^{+}_{G_{1}}(a)$ all lie on a
single face of $G_{1}$ (in that order), so $D_{a}$ and $D_{b}$ have a common
vertex. Similarly as in the proof of Lemma 7.3, we can conclude that in fact
there exists a $a\to b$ detour of $x$ in $G_{1}$. Hence, indeed $p_{i}=a$ and
$p_{j}=b$.

It remains to show how to compute the vertices $a,b$, as defined above, for
all $x\in V(P)$. Let us focus on computing the values $a$; the values $b$ can
be computed by proceeding symmetrically. We first compute the values
$\alpha^{+}_{G_{1}}(w)$ for all $w\in V(P)$ in linear time using Lemma 7.6.

Now, the problem can be rephrased in a more abstract way as follows: given an
array $t[1..\ell]$, compute for each $i=1,\ldots,\ell$ the value
$h[i]=\max\\{j:j<i\land t[j]>i\\}$. We solve this problem by processing $t$
left-to-right and maintaining a certain subset $S$ of indices $j<i$ that
surely contains all the values $h[i],\ldots,h[\ell]$ that are less than $i$.
The indices of $S$ are stored in a stack sorted bottom-to-top. Additionally we
maintain the invariant that for $S=\\{i_{1},\ldots,i_{s}\\}$, where
$i_{1}<\ldots<i_{s}$, we have $t[i_{1}]>\ldots>t[i_{s}]$.

Initially, $S$ is empty. Suppose we process some $i$. By the invariants posed
on $S$ we know that $h[i]\in S$. Let $i_{s}$ be the top element of the stack.
If $t[i_{s}]>i$ then $h[i]=i_{s}$ since $i_{s}=\max{S}$. Otherwise
$t[i_{s}]\leq i$. Hence, we also have $t[i_{s}]\leq j$ for all $j\geq i$, so
$h[j]\neq i_{s}$. Consequently, we can remove $i_{s}$ from $S$ (by popping it
from the top of the stack) without breaking the invariants posed on $S$. We
repeat the process until $S$ is empty or $t[i_{s}]>i$. If $S$ becomes empty,
we set $h[i]=-\infty$, otherwise $h[i]=i_{s}$. At this point, $S$ contains
values $h[j]$ for all $j>i$ such that $h[j]<i$.

In order to move to the next $i$, we need $S$ to contain values $h[j]$ for all
$j>i$ such that $h[j]\leq i$ and the stack storing $S$ has to be sorted top to
bottom according to the $t$-values. If $t[i_{s}]>t[i]$, we push $i$ to $S$ and
finish. Suppose $t[i_{s}]\leq t[i]$. We show that $h[j]\neq t[i_{s}]$ for
$j>i$ and thus we can safely remove $i_{s}$ from $S$. Assume the contrary,
i.e., $h[j]=i_{s}$ for some $j>i$. But then $t[i]\geq t[h[j]]>j$ and
$h[j]=\max\\{j^{\prime}:j^{\prime}<j\land t[j^{\prime}]>i\\}\geq i>h[j]$, a
contradiction.

The running time of this algorithms is clearly linear in $\ell$ plus the
number of stack operations. The total number of stack operations is linear in
the number of indices pushed to to the stack, i.e., no more than $\ell$. ∎

###  7.3 Simplifying paths

In this section we devise a few lemmas that will allow the query procedure to
consider only paths of a very special form.

Let $R$ be any path. Let $enter({R})$ be the first vertex of $R$ that
additionally lies on $P$. Similarly, let $leave({R})$ be the last vertex of
$R$ that additionally lies on $P$. Let $min({R})$ ($max({R})$) be the earliest
(latest) vertex of $V(R)\cap V(P)$ wrt. to $\preceq_{P}$.

######  Lemma 7.8.

Let $a,b$ be some two vertices of $P$ such that $x\notin V(P[a,b])$. Let
$Q=LR$ be any $u\to v$ path in $G-x$ satisfying $enter({Q})\in V(P[a,b])$ and
such that $L$ is a satellite $u\to enter({Q})$ path. Let
$u^{\prime}=first_{G-x}(first^{*}_{G}(u,a,b),a,b)$.

Then $Q$ does not go through the vertices of $P[a,b]$ earlier than
$u^{\prime}$. Moreover, there exists a $u\to v$ path $Q^{\prime}=L^{\prime}R$
in $G-x$ such that $enter({Q^{\prime}})\in V(P[a,b])$, $u^{\prime}\in
V(L^{\prime})$ and $leave({Q^{\prime}})=leave({Q})$.

###### Proof.

First note that by $enter({Q})\in V(P[a,b])$, $first^{*}_{G}(u,a,b)$ is in
fact defined. Hence $u^{\prime}\in V(P[a,b])$ also exists and
$u^{\prime}\preceq first^{*}_{G}(v,a,b)$.

Suppose $Q$ goes through a vertex $u^{\prime\prime}$ of $P[a,b]$ earlier than
$u^{\prime}$. Then there exists an $enter({Q})\to u^{\prime\prime}$ path in
$G-x$. We have $first^{*}_{G}(u,a,b)\preceq enter({Q})$. Since $x\notin
V(P[a,b])$, there exists a $first^{*}_{G}(u,a,b)\to enter({Q})$ path (e.g.,
$P[first^{*}_{G}(u,a,b),enter({Q})]$) in $G-x$. It follows that there exists a
$first^{*}_{G}(u,a,b)\to u^{\prime\prime}$ path in $G-x$, which contradicts
the definition of $u^{\prime}$.

To finish the proof, note that it is sufficient to set $L^{\prime}$ to be a
concatenation of a satellite $u\to first^{*}_{G}(u,a,b)$ path, any
$first^{*}_{G}(u,a,b)\to u^{\prime}$ path in $G-x$ and
$P[u^{\prime},enter({Q})]$. Note that $L^{\prime}$ is not necessarily simple.
∎

######  Lemma 7.9.

Let $Q=LR$ be any $u\to v$ path in $G-x$ satisfying $enter({Q})\prec x$ and
such that $L$ is a $u\to enter({Q})$ satellite path. Let
$u^{\prime}=first_{G-x}(first^{*}_{G}(u))$. Then $u^{\prime}\preceq min({Q})$.
Moreover, there exists a $u\to v$ path $Q^{\prime}=L^{\prime}R$ in $G-x$ such
that $enter({Q^{\prime}})\prec x$,
$min({L^{\prime}})=min({Q^{\prime}})=u^{\prime}$, and
$leave({Q^{\prime}})=leave({Q})$.

###### Proof.

It is enough to apply Lemma 7.8 to $a=p_{1}$ and $b$ equal to the vertex
preceding $x$ on $P$. ∎

######  Lemma 7.10.

Let $Q=LR$ be any $u\to v$ path in $G-x$ satisfying $x\prec leave({Q})$ and
such that $R$ is a $leave({Q})\to v$ satellite path. Let
$v^{\prime}=last_{G-x}(last^{*}_{G}(v))$. Then $max({Q})\preceq v^{\prime}$.
Moreover, there exists a $u\to v$ path $Q^{\prime}=LR^{\prime}$ in $G-x$ such
that $x\prec leave({Q^{\prime}})$,
$max({R^{\prime}})=max({Q^{\prime}})=v^{\prime}$,
$enter({Q^{\prime}})=enter({Q})$.

###### Proof.

This lemma is symmetric to Lemma 7.9 and therefore can be proved analogously.
∎

######  Lemma 7.11.

Suppose a directed path $Q=u\to v$ in $G-x$ such that $min({Q})\prec x\prec
max({Q})$ can be represented as $Q_{1}RQ_{2}$, where $R$ is a $min({Q})\to
max({Q})$ path. Then there is a $u\to v$ path $Q^{\prime}$ in $G-x$ that can
be represented as $Q_{1}P_{1}P_{2}P_{3}Q_{2}$, where $P_{1}$ and $P_{3}$ are
(possibly empty) subpaths of $P$ and $P_{2}$ is a minimal detour of $x$.

###### Proof.

Let $R=R_{1}R_{2}$, where $R_{2}$ starts at $y$, $min({Q})\preceq y\prec x$
and $R_{2}$ does not go through any other vertices of $P[min({Q}),x]$. Such an
$y$ exists since $min({Q})\prec x\prec max({Q})$. Observe that $R_{2}$ starts
with some detour $D=y\to z$ of $x$, where $z\in P[x,max({Q})]$. Hence $R$ can
be rewritten as $R_{1}DR_{3}$, where $R_{3}=z\to max({Q})$ is possibly an
empty path. If $D$ is not minimal, let $D^{\prime}=y^{\prime}\to z^{\prime}$
be a minimal detour of $x$ such that $y\preceq y^{\prime}\prec x\prec
z^{\prime}\preceq z$. Note that since $min({Q})\preceq y\preceq
y^{\prime}\prec x$ and $x\prec z^{\prime}\preceq z\preceq max({Q})$,
$P[min({Q}),y^{\prime}]D^{\prime}P[z^{\prime},max({Q})]$ is a $min({Q})\to
max({Q})$ path in $G-x$. ∎

###  7.4 The query algorithm

Finally we are ready to describe our query algorithm. Recall that we want to
efficiently check whether there exists a $u\to v$ path $Q$ in $G-x$ that goes
through $V(P)$, for $x\in V(P)$. We consider cases based on the configuration
of $enter({Q})$, $leave({Q})$ and $x$ on $P$.

  1. 1.

Suppose there exists such a path $Q$ that $enter({Q})\prec x$ and $x\prec
leave({Q})$. Let $u^{\prime}=first_{G-x}(first^{*}_{G}(u))$ as in Lemma 7.9.
Since $first^{*}_{G}(u)\prec x$, $u^{\prime}$ can be computed in $O(\log{n})$
time by first using Lemma 7.4 to compute $first^{*}_{G}(u)$ and then using
Lemma 7.5.

By Lemma 7.9, there exists a $u\to v$ path $Q^{\prime}=L^{\prime}R$ in $G-x$
such that $enter({Q^{\prime}})\prec x$,
$min({L^{\prime}})=min({Q^{\prime}})=u^{\prime}$ and $x\prec
leave({Q^{\prime}})$. Let $v^{\prime}=last_{G-x}(v,last^{*}_{G}(v))$.
Similarly, since $x\prec leave({Q^{\prime}})\preceq last^{*}_{G}(v)$,
$v^{\prime}$ can be computed in $O(\log{n})$ time by Lemmas 7.4 and 7.5. By
Lemma 7.10, there exists a $u\to v$ path
$Q^{\prime\prime}=L^{\prime}R^{\prime}$ in $G-x$ such that
$enter({Q^{\prime\prime}})\prec x$, $x\prec leave({Q^{\prime\prime}})$,
$max({Q^{\prime\prime}})=v^{\prime}$. Since $min({L^{\prime}})=u^{\prime}$ and
$Q^{\prime\prime}$ cannot go through a vertex of $P$ earlier then $u^{\prime}$
(by Lemma 7.9), we also have $min({Q^{\prime\prime}})=u^{\prime}$.

As we have $u^{\prime}=min({Q^{\prime\prime}})\prec x\prec
max({Q^{\prime\prime}})=v^{\prime}$, we can apply Lemma 7.11. In order to find
a $u\to v$ path in $G-x$ such that $enter({Q})\prec x$ and $x\prec
leave({Q})$, we only need to check whether there exits a path
$P_{1}P_{2}P_{3}=u^{\prime}\to v^{\prime}$ such that $P_{1}$ and $P_{3}$ are
subpaths of $P$ and $P_{2}$ is a minimal detour of $x$. By Lemma 7.3, there
are only two minimal detour pairs $(e,f)$ of $x$. Assuming $P_{2}=e\to f$,
$P_{1}$ exists if and only if $u^{\prime}\preceq e$. Similarly $P_{3}$ exists
if and only if $f\preceq v^{\prime}$. Hence, each of at most two minimal
detour pairs can be checked in constant time.

  2. 2.

Suppose that $enter({Q})\prec x$ and $leave({Q})\prec x$. Similarly as in the
previous case, by Lemma 7.9 (and putting $Q:=Q^{\prime}$) we can assume that
the sought path $Q$ goes through $u^{\prime}=first_{G-x}(first^{*}_{G}(u))$
and $min({Q})=u^{\prime}$. As before, $u^{\prime}\prec x$ can be reached from
$u$ in $G-x$. Now, since $u^{\prime}=min({Q})\preceq leave({Q})\prec x$, we
can limit our attention to such paths $Q$ that the subpath from $u^{\prime}$
to $leave({Q})$ of $Q$ is actually a subpath of $P$. Hence, in order to check
if such $Q$ exists, we only need to check whether there is a satellite path
$z\to v$, where $u^{\prime}\preceq z\prec x$. In other words we can check
whether $last^{*}_{G}(v,u^{\prime},x^{\prime})$, where $x^{\prime}$ is a
predecessor of $x$ on $P$, exists. This can be done in $O(\log{n})$ time using
Lemma 7.4.

  3. 3.

Suppose that $x\prec enter({Q})$ and $x\prec leave({Q})$. This case is
symmetric to the preceding case: we analogously check whether $u$ can reach
$v^{\prime}$ by a satellite path and a subpath of $P$.

  4. 4.

Finally, suppose $x\prec enter({Q})$ and $leave({Q})\prec x$. Let $y$ be the
vertex following $x$ on $P$. Let us now apply Lemma 7.8 for $a=y$ and
$b=p_{\ell}$, and let
$u^{\prime}=first_{G-x}(first^{*}_{G}(u,y,p_{\ell}),y,p_{\ell})$ be as in
Lemma 7.8. $u^{\prime}$ can be again computed in $O(\log{n})$ time by first
using Lemma 7.4 to obtain $first^{*}_{G}(u,y,p_{\ell})$ and then applying
Lemma 7.5. We conclude that there exists a $u\to v$ path $Q^{\prime}$ in $G-x$
that goes through $u^{\prime}$, does not go through vertices of $P$ between
$x$ and $u^{\prime}$, and satisfies $leave({Q^{\prime}})\prec x$. Note that
since $Q^{\prime}$ last departs from $V(P)$ at a vertex earlier than $x$, and
simultaneously goes through $u^{\prime}\in V(P[y,p_{\ell}])$, $Q^{\prime}$ can
be written as $Q^{\prime}=YRST$, where $R=u^{\prime}\to s$, $S=s\to t$, $s\in
V(P[y,p_{\ell}])$, $t\in V(P)$, $t\prec x$, and $S$ is a satellite path.

Let $t^{\prime}$ be the earliest vertex of $P$ such that $t^{\prime}$ can be
reached from $u^{\prime}$ by a path of the form $R^{\prime}S^{\prime}$, where
$R^{\prime}$ is a subpath of $P$ and $S^{\prime}$ is a satellite path. Observe
that we have $t^{\prime}\preceq t$, since the path $R$ does not go through any
vertex between $x$ and $u^{\prime}$ on $P$ and thus $t$ can be reached from
$u^{\prime}$ by a path $P[u^{\prime},s]S$. Note also that there exists a $u\to
v$ path $Q^{\prime\prime}$ avoiding $x$ such that
$Q^{\prime\prime}=YR^{\prime}S^{\prime}T^{\prime}$: if we set
$T^{\prime}=P[t^{\prime},t]T$, clearly all
$Y,R^{\prime},S^{\prime},T^{\prime}$ avoid $x$.

Furthermore, note that we could replace path $T^{\prime}$ with any
$t^{\prime}\to v$ path $T^{\prime\prime}$ in $G-x$ satisfying
$leave({T^{\prime\prime}})\prec x$ and would still obtain a $u\to v$ path in
$G-x$. Note that $enter({T^{\prime\prime}})=t^{\prime}$, so clearly
$enter({T^{\prime\prime}})\prec x$. Checking if any such path
$T^{\prime\prime}=t^{\prime}\to v$ exists can be performed as in case 2.

It remains to show how to compute the earliest possible vertex $t^{\prime}$
given $u^{\prime}$. Observe that we want to pick such $s\in
P[u^{\prime},p_{\ell}]$ that can reach the earliest vertex of $P$ using a
satellite path. To this end we need to find the earliest out of the earliest
backwards jumps of all vertices of $P[u^{\prime},p_{\ell}]$. This can be
computed in $O(1)$ time, after preprocessing the earliest backwards jumps for
all suffixes of $P$ in linear time.

To sum up, the query procedure tries to find a $u\to v$ path $Q$ in $G-x$ for
each of the above four configurations of $enter({Q})$, $leave({Q})$ and $x$.
Each of the cases is handled in $O(\log{n})$ time.

##  8 2-Reachability Queries

To answer 2-reachability queries we reuse the recursive approach and extend
the data structure of Section 4. Suppose we want to know whether there exist
two vertex-disjoint paths from $u$ to $v$ in some graph $G$ with suppressed
set $A$ and separator $S_{ab}$ that arises in the recursive decomposition.
Recall that $S_{ab}-A$ can be decomposed into $O(1)$ simple directed paths
$P_{1},\ldots,P_{k}$ in $G-A$.

First suppose that there is no $P_{i}$ such that some $u\to v$ path goes
through $V(P_{i})$ in $G-A$. Then either no $u\to v$ path in $G-A$ exists at
all, or it is contained in at most one child subgraph $G[V_{i}]-A$
($i\in\\{1,2\\}$), where $V_{1},V_{2}$ are the subsets of $V(G)$ strictly on
one side of the separator. In this case, in $O(1)$ time we reduce our problem
to searching for two vertex-disjoint $u\to v$ paths in a graph
$G^{\prime}[V_{i}\cup\\{r^{\prime}\\}]$ with suppressed set $(A\cap
V_{i})\cup\\{r^{\prime}\\}$, as described in Section 3.

Otherwise, there exists a $u\to v$ path in $G-A$ that goes through
$V(S_{ab})$. We will handle this case without further recursive calls (so, the
time needed to reduce the original problem to this case is clearly
$O(\log{n})$). Observe that this guarantees that, in fact, no $u\to v$ path
goes through a vertex of $A$ in $G$. This is because the suppressed set can
only contain (possibly contracted) vertices of the separators in the ancestors
of $G$ in the recursion tree, and no $u\to v$ path could go through these
separators. Moreover, every $u\to v$ path in the input graph $G_{0}$ (i.e.,
$G_{0}$ denotes the ancestor of $G$ in the recursion tree that is the root) is
preserved in $G$. Consequently, for any $x\in V(G)$ we can test whether there
exists a $u\to v$ path in $G-x$ by issuing the $(u,v,x)$ query to the
1-sensitivity oracle built for the input graph $G_{0}$.

In fact, we will focus on finding some $x\in V(G)$ that lies on all $u\to v$
paths in $G$ (equivalently, in $G-A$). In other words, we will be looking for
a _separating vertex_ certifying that $v$ is not 2-reachable from $u$. There
are a few cases to consider.

First, assume that we can find two paths $P_{i},P_{j}$, $i\neq j$ such that
there exists both a $u\to v$ path through $P_{i}$ and a $u\to v$ path through
$P_{j}$ in $G$. If some vertex $x\in V(G)$ lies on all $u\to v$ paths in $G$,
then either $x\in V(P_{i})\cap V(P_{j})$ or $x\in V(G)\setminus V(P_{i})$ or
$x\in V(G)\setminus V(P_{j})$. We can check all $x\in V(P_{i})\cap V(P_{j})$
in $O(\log{n})$ time using only $O(1)$ queries to our 1-sensitivity
reachability oracle of Theorem 1.1, since $|V(P_{i})\cap V(P_{j})|=O(1)$. In
Section 8.1 we show that the two latter cases, i.e., finding a separating
vertex outside a path through which one can reach $v$ from $u$, can be handled
separately in $O(\log{n})$ time after additional linear preprocessing.

Finally, suppose there is a unique path $P_{i}$ such that there exists a $u\to
v$ path through $V(P_{i})$ in $G$. As we mentioned above, if some vertex $x\in
V(G)\setminus V(P_{i})$ lies on all $u\to v$ paths in $G$, it can be found as
described in Section 8.1. Suppose that $x\in V(P_{i})$. Note that by the
uniqueness of $i$, all $u\to v$ paths in $G$ are preserved in
$G[\bar{V_{i}}]$, where $\bar{V_{i}}=V(G)\setminus V(S_{ab})\cup V(P_{i})$.
Similarly to Section 4, we can assume that $u$ and $v$ lie in a single
connected component of $G[\bar{V_{i}}]$ and the endpoints of $P_{i}$ lie on a
single face of that component. In Section 8.2 we show that these assumptions
enable us to find a separating vertex on a path through which one can reach
$v$ from $u$ in $O(\log^{2+o(1)}{n})$ time after additional
$O(n\log^{5+o(1)}{n})$ preprocessing and using $O(n\log^{2+o(1)}{n})$ space
(per node of the recursion tree). The total preprocessing time and space
consumption can be analyzed analogously as in Section 3. The following theorem
summarizes our data structure. See 1.2

###  8.1 Looking for a separating vertex outside the path

Let $G$ be a plane digraph and let $p_{1}\ldots p_{\ell}=P\subseteq G$ be a
directed path. Our goal in this section is to support queries of the following
form: for any $u,v\in V(G)$ such that there exists a $u\to v$ path going
through $V(P)$ in $G$, find a vertex $x\in V(G)\setminus V(P)$ such that all
$u\to v$ paths in $G$ go through $x$, or decide there is no such vertex. We
start by fixing notation similar to that from Section 6

For $i=\ell,\ldots,1$ let $L_{i}$ be the subset of $V(G)\setminus V(P)$
reachable from $p_{i}$ by a satellite path (wrt. $P$), minus
$\bigcup_{j=i+1}^{\ell}L_{j}$. Denote by $D_{i}$ the dominator tree of
$G[p_{i}\cup L_{i}]$.

Analogously, for $i=1,\ldots,\ell$, let ${L}^{\text{R}}_{i}$ be the subset of
$V(G)\setminus V(P)$ that can reach $p_{i}$ by a satellite path, minus
$\bigcup_{j=1}^{i-1}{L}^{\text{R}}_{j}$. Denote by ${D}^{\text{R}}_{i}$ the
dominator tree of ${G}^{\text{R}}[p_{i}\cup{L}^{\text{R}}_{i}]$.

All the sets $L_{i},{L}^{\text{R}}_{i}$ and all dominator trees
$D_{i},{D}^{\text{R}}_{i}$ can be computed in linear time similarly as in
Section 6. Let the functions $first_{G},last_{G},first^{*}_{G},last^{*}_{G}$
be defined (wrt. $P$) as in Section 6. For brevity we use $\prec$ to denote
the order $\prec_{P}$.

We start with the first key lemma that allows us to reduce the case when the
vertices $first^{*}_{G}(u)$ and $first^{*}_{G}(v)$ are not strongly connected
to querying for an existence of a $u\to v$ path in $G-x$ for only two possible
vertices $x$ and using the 1-sensitivity data structure that we have
developed.

######  Lemma 8.1.

Let $u,v\in V(G)$. Suppose the following conditions are satisfied:

  1. 1.

there exists a $u\to v$ path in $G$ that goes through $V(P)$,

  2. 2.

$first^{*}_{G}(u)=p_{i}$ and $last^{*}_{G}(v)=p_{j}$ are not strongly
connected in $G$,

  3. 3.

there exists $x\in V(G)\setminus V(P)\setminus\\{u,v\\}$ such that all $u\to
v$ paths in $G$ go through $x$.

Then either all $u\to v$ paths in $G$ go through the parent of $u$ in
${D}^{\text{R}}_{i}$, or all of them go through the parent of $v$ in $D_{j}$.

###### Proof.

Since $u$ can reach $v$ through $V(P)$, $first^{*}_{G}(u)=p_{i}$ and
$last^{*}_{G}(v)=p_{j}$ indeed exist. Moreover, for the same reason some path
$Q$ from $first_{G}(u)$ to $last_{G}(v)$ exists. Clearly, there exist some
paths $Q_{u}=first^{*}_{G}(u)\to first_{G}(u)$ and $Q_{v}=last_{G}(v)\to
last^{*}_{G}(v)$ in $G$. If we had $last^{*}_{G}(v)\preceq first^{*}_{G}(u)$,
then $Q_{v}\cdot P[last^{*}_{G}(v),first^{*}_{G}(u)]\cdot Q_{u}\cdot Q$ would
form a cycle in $G$ and thus $last^{*}_{G}(v)$ and $first^{*}_{G}(u)$ would be
strongly connected, a contradiction. Hence, we obtain $first^{*}_{G}(u)\prec
last^{*}_{G}(v)$.

If there were satellite paths $R=u\to first^{*}_{G}(u)$ and
$T=last^{*}_{G}(v)\to v$ such that $x$ is a vertex of neither $R$ nor $T$,
then $RP[first^{*}_{G}(u),last^{*}_{G}(v)]T$ would be a $u\to v$ path not
going through $x$, which is impossible. Assume wlog. that $x$ lies on all
$last^{*}_{G}(v)\to v$ satellite paths in $G$ (the proof when $x$ lies on all
$u\to first^{*}_{G}(u)$ satellite paths is symmetric).

Let $w$ be the parent of $v$ in $D_{j}$. Note that since $x\notin V(P)$ and
$x$ lies on all $last^{*}_{G}(v)\to v$ satellite paths, we have
$last^{*}_{G}(x)=last^{*}_{G}(v)$ and hence $x\in L_{j}$. Moreover, since
$x\neq v$, $x$ is a non-root ancestor of $v$ in $D_{j}$. It follows that
$w\neq last^{*}_{G}(v)$ and, by Lemma 5.1, any $x\to v$ satellite path goes
through $w$.

We will now prove that all $u\to v$ paths in $G$ go through $w$. To this end,
suppose the contrary, that there exists a $u\to v$ path $Y$ that does not go
through $w$. First consider the case when $V(Y)\cap V(P)\neq\emptyset$. $Y$
can be expressed as $Y^{\prime}Z$, where $Z$ is a satellite path $p\to v$, for
some $p\in V(P)$. By the definition of $last^{*}_{G}(v)$, $p\preceq
last^{*}_{G}(v)$. If $x\in V(Z)$, then $w\in V(Z)$, since any $x\to v$
satellite path goes through $w$, a contradiction. Hence $x\notin V(Z)$ and
thus $p\neq last^{*}_{G}(v)$, which implies $p\prec last^{*}_{G}(v)$.

But $Y$ has to go through $x$, so there exists a path $x\to p$ in $G$. Since
$x$ is reachable from $last^{*}_{G}(v)$ (as $x\in L_{j}$) and
$last^{*}_{G}(v)$ is reachable from $p$, we conclude that $p$ and
$last^{*}_{G}(v)$ are strongly connected. If we had $p\preceq
first^{*}_{G}(u)$, then Lemma 6.3 would imply that $first^{*}_{G}(u)$ and
$last^{*}_{G}(v)$ are strongly connected, a contradiction. Hence
$first^{*}_{G}(u)\prec p$.

Take any satellite path $S=u\to first^{*}_{G}(u)$. If $x\notin V(S)$, then
$S\cdot P[first^{*}_{G}(u),p]\cdot Z$ is a $u\to v$ path not going through