# Fully Dynamic Strongly Connected Components in Planar Digraphs

Adam Karczmarz University of Warsaw and IDEAS NCBR, Poland.
<EMAIL_ADDRESS>Partially supported by the ERC CoG grant TUgbOAT no
772346 and the National Science Centre (NCN) grant no. 2022/47/D/ST6/02184.
Marcin Smulewicz University of Warsaw, Poland<EMAIL_ADDRESS>
###### Abstract

In this paper, we consider maintaining strongly connected components (SCCs) of
a directed planar graph subject to edge insertions and deletions. We show a
data structure maintaining an implicit representation of the SCCs within
$\widetilde{O}(n^{6/7})$ worst-case time per update. The data structure
supports, in $O(\log^{2}{n})$ time, reporting vertices of any specified SCC
(with constant overhead per reported vertex) and aggregating vertex
information (e.g., computing the maximum label) over all the vertices of that
SCC. Furthermore, it can maintain global information about the structure of
SCCs, such as the number of SCCs, or the size of the largest SCC.

To the best of our knowledge, no fully dynamic SCCs data structures with
sublinear update time have been previously known for any major subclass of
digraphs. Our result should be contrasted with the $n^{1-o(1)}$ amortized
update time lower bound conditional on SETH [AW14], which holds even for
dynamically maintaining whether a general digraph has more than two SCCs.

##  1 Introduction

Two vertices of a directed graph $G=(V,E)$ are called strongly connected if
they can reach each other using paths in $G$. Pairwise strong connectivity is
an equivalence relation and the strongly connected components (SCCs) of $G$
are its equivalence classes. Computing the SCCs is among the most classical
and fundamental algorithmic problems on digraphs and there exists a number of
linear-time algorithms for that [Gab00, Sha81, Tar72]. Therefore, it is no
surprise that _maintaining_ SCCs has been one of the most actively studied
problems on _dynamic directed graphs_ [AW14, BFGT16, BDP21, BGS20, BPW19,
CHI+16, CKL+23, HKM+12, IKŁS17, KS23, Łą13, RZ08].

When maintaining the strongly connected components, the information we care
about may vary. First, we could be interested in efficiently answering
_pairwise_ strong connectivity queries: given $u,v\in V$, decide whether $u$
and $v$ are strongly connected. Pairwise strong connectivity queries, however,
cannot easily provide any information about the _global_ structure of SCCs
(such as the number of SCCs, the size of the largest SCC). Neither they
enable, e.g., listing the vertices strongly connected to some $u\in V$. This
is why, in the following, we distinguish between _dynamic pairwise strong
connectivity_ and _dynamic SCCs_ data structures which provide a more global
view. In particular, all the data about the SCCs can be easily accessed if the
SCCs are maintained _explicitly_ , e.g., if the SCC identifier of every vertex
is stored at all times and explicitly updated.

###  1.1 Previous work

In the following, let $n=|V|$ and $m=|E|$. Dynamic graph data structures are
traditionally studies in _incremental_ , _decremental_ or _fully dynamic_
settings, which permit the graph to evolve by either only edge insertions,
only deletions, or both, respectively. A decremental data structure
maintaining SCCs with near-optimal total update time is known [BPW19]. Very
recently, a deterministic data structure with $m^{1+o(1)}$ total update time
has been obtained also for the incremental setting [CKL+23]. Both these state-
of-the art data structures maintain the SCCs explicitly.

The _fully dynamic_ variant – which is our focus in this paper – although the
most natural, has been studied the least. First of all, there is strong
evidence that a non-trivial dynamic SCCs data structure for sparse graphs
cannot exist. If the SCCs have to be maintained explicitly, then a single
update can cause a rather dramatic $\Omega(n)$-sized amortized change in the
set of SCCs111Consider a directed cycle and switching its arbitrary single
edge on and off.. As a result, an explicit update may be asymptotically as
costly as recomputing SCCs from scratch. This argument – applicable also for
maintaining _connected components_ of an undirected graph – does not exclude
the possibility of maintaining an _implicit_ representation of the SCCs in
sublinear time, though. After all, there exist very efficient fully dynamic
connectivity data structures, e.g., [HdLT01, HHK+23, Wul13], typically
maintaining also an explicit spanning forest which allows retrieving any
’’global‘‘ component-wise information one can think of rather easily. However,
[AW14] showed that even for maintaining a single-bit information whether $G$
has _more than two SCCs_ , a data structure with $O(n^{1-\epsilon})$ amortized
time is unlikely, as it would break the Orthogonal Vectors conjecture implied
by the SETH [IP01, Wil05].222In [AW14], a conditional lower bound of the same
strength is also derived for the dynamic #SSR problem where the goal is to
dynamically count vertices reachable from a source $s\in V$. This considerably
limits the possible global information about the SCCs that can be maintained
within sublinear time per update.

For denser graphs, [AW14] also proved that maintaining essentially any (even
pairwise) information about SCCs dynamically within truly subquadratic update
time has to rely on fast matrix multiplication. And indeed, that pairwise
strong connectivity can be maintained this way follows easily from the dynamic
matrix inverse-based dynamic $st$-reachability data structures [vdBNS19,
San05]. More recently, [KS23] showed that in fact SCCs can be maintained
explicitly in $O(n^{1.529})$ worst-case time per update. They also proved that
maintaining whether $G$ has just a single SCC (_dynamic SC_) is
easier333Interestingly, the SETH-based lower bound of [AW14] does not apply to
the dynamic SC problem. and can be achieved within $O(n^{1.406})$ worst-case
time per update. Both these bounds are tight conditional on the appropriate
variants [vdBNS19] of the OMv conjecture [HKNS15].

In summary, the complexity of maintaining SCCs in general directed graphs is
rather well-understood now. In partially dynamic settings, the known bounds
are near optimal unconditionally, whereas in the fully dynamic setting, the
picture appears complete unless some popular hardness conjectures are proven
wrong. In particular, for general sparse digraphs, no (asymptotically) non-
trivial fully dynamic SCCs data structure can exist.

##### Planar graphs.

It is thus natural to ask whether non-trivial dynamic SCCs data structures are
possible if we limit our attention to some significant class of sparse
digraphs. And indeed, this question has been partially addressed for _planar
digraphs_ in the past. Since pairwise $s,t$-strong connectivity queries reduce
to two $s,t$-reachability queries, the known planar dynamic reachability data
structures [DS07, Sub93] imply that sublinear ($\widetilde{O}(n^{2/3})$ or
$\widetilde{O}(\sqrt{n})$-time, depending on whether embedding-respecting
insertions are required) updates/queries are possible for _pairwise_ strong
connectivity. Another trade-off for dynamic pairwise strong connectivity has
been showed by [CK22]. Namely, they showed a fully dynamic data structure for
planar graphs with $\widetilde{O}(n^{4/5})$ worst-case update time that can
produce an identifier $s_{v}$ of an SCC of a given query vertex $v$ in
$O(\log^{2}{n})$ time. Whereas this is slightly more general444Than answering
pairwise strong connectivity queries. Using the SCC-identifiers, one can,
e.g., partition any $k$ vertices of $G$ into strongly connected classes in
$\widetilde{O}(k)$ time, whereas using pairwise queries this requires
$\Theta(k^{2})$ queries., it still not powerful enough to enable efficiently
maintaining any of the global data about the SCCs of a dynamic planar digraph
such as the SCCs count.

To the best of our knowledge, the question whether a more robust – that is,
giving a more ’’global‘‘ perspective on the SCCs beyond only supporting
pairwise queries – fully dynamic SCCs data structure for planar digraphs (or
digraphs from any other interesting class) with sublinear update time is
possible has not been addressed before.

###  1.2 Our results

In this paper, we address the posed question in the case of planar directed
graphs. Specifically, our main result is a dynamic SCCs data structure
summarized by the following theorem.

######  Theorem 1.1.

Let $G$ be a planar digraph subject to planarity-preserving edge insertions
and deletions. There exists a data structure maintaining the strongly
connected components of $G$ implicitly in $\widetilde{O}(n^{6/7})$ worst-case
time per update. Specifically:

  * •

The data structure maintains the number of SCCs and the size of the largest
SCC in $G$.

  * •

For any query vertex $v$, in $O(\log^{2}{n})$ time the data structure can
compute the size of the SCC of $v$, and enable reporting the elements of the
SCC of $v$ in $O(1)$ worst-case time per element.

In particular, Theorem 1.1 constitutes the first known fully dynamic SCCs data
structure with sublinear update time for any significant class of sparse
digraphs. It also shows that the conditional lower bound of [AW14] does not
hold in planar digraphs.

The data structure of Theorem 1.1 is deterministic and does not require the
edge insertions to respect any fixed embedding of the graph (this also applies
to side results discussed below). Obtaining more efficient data structures for
fully dynamic embedding-respecting updates is an interesting direction (see,
e.g., [DS07]) that is beyond the scope of this paper.

##### Related problems.

Motivated by the discrepancies between the known bounds for dynamic SCCs and
dynamic SC in general digraphs (both from the lower- [AW14] and upper bounds
[KS23] perspective), we also complement Theorem 1.1 with a significantly
simpler and faster data structure suggesting that the dynamic SC might be
easier (than dynamic SCCs) in planar digraphs as well.555Clearly, one could
use Theorem 1.1 for dynamic SC as well.

######  Lemma 1.2.

Let $G$ be a planar digraph subject to planarity-preserving edge insertions
and deletions. One can maintain whether $G$ has a single SCC in
$\widetilde{O}(n^{2/3})$ worst-case time per update.

Similarly, one could ask how _dynamic #SSR_ (i.e., counting vertices reachable
from a single source) relates to dynamic SCCs in planar digraphs. Especially
since:

  1. (1)

in general directed graphs, dynamic SCCs and dynamic #SSR currently have
matching lower- [AW14, vdBNS19] and upper bounds [KS23, San05] (up to
polylogarithmic factors);

  2. (2)

the former problem is at least as hard as the latter in the sense that dynamic
#SSR reduces to dynamic SCCs in general graphs easily666Consider the graph
$G^{\prime}$ obtained from $G$ by adding a supersink $t$ with a single
outgoing edge $ts$ and incoming edges $vt$ for all $v\in V$. Then $v\in V$ is
reachable from $s$ in $G$ iff $s$ and $v$ are strongly connected in
$G^{\prime}$. See also [vdBNS19]., whereas an opposite reduction is not known.

Unfortunately, the aforementioned reduction of dynamic #SSR to dynamic SCCs
breaks planarity rather badly. Interestingly, the _path net_ technique we
develop to obtain Theorem 1.1 does not seem to work for counting
’’asymmetric‘‘ reachabilities from a single source.

Nevertheless, we observe that the Voronoi diagram machinery developed for
computing the diameter of a planar graph [GKM+21] almost immediately yields a
more efficient data structure for dynamic #SSR in planar digraphs with
$\widetilde{O}(n^{4/5})$ update time; see Lemma 6.1 in Section 6. It is worth
noting that Voronoi diagrams-based techniques (as developed for distance
oracles [GMWW18]) have been used in the pairwise strong connectivity data
structure [CK22]. However, as we discuss later on, it is not clear how to
apply those for the dynamic SCCs problem. This is why Theorem 1.1 relies on a
completely different path net approach developed in this paper.

##### Organization.

We review some standard planar graph tools in Section 2. Then, as a warm-up,
we show the data structure for dynamic SC in Section 3. In Section 4 we define
the path net data structure and show how it can be used to obtain a dynamic
SCCs data structure. In Section 5 we describe the path net data structure in
detail. Finally, Section 6 is devoted to the fully dynamic #SSR problem in
planar digraphs.

##  2 Preliminaries

In this paper we deal with _directed_ graphs. We write $V(G)$ and $E(G)$ to
denote the sets of vertices and edges of $G$, respectively. We omit $G$ when
the graph in consideration is clear from the context. A graph $H$ is a
_subgraph_ of $G$, which we denote by $H\subseteq G$, iff $V(H)\subseteq V(G)$
and $E(H)\subseteq E(G)$. We write $e=uv\in E(G)$ when referring to edges of
$G$. By ${G}^{\textrm{R}}$ we denote $G$ with edges reversed.

A sequence of vertices $P=v_{1}\ldots v_{k}$, where $k\geq 1$, is called an
$s\to t$ path in $G$ if $s=v_{1}$, $v_{k}=t$ and there is an edge
$v_{i}v_{i+1}$ in $G$ for each $i=1,\ldots,k-1$. We sometimes view a path $P$
as a subgraph of $G$ with vertices $\\{v_{1},\ldots,v_{k}\\}$ and (possibly
zero) edges $\\{v_{1}v_{2},\ldots,v_{k-1}v_{k}\\}$. For convenience, we
sometimes consider a single edge $uv$ a path. If $P_{1}$ is a $u\to v$ path
and $P_{2}$ is a $v\to w$ path, we denote by $P_{1}\cdot P_{2}$ (or simply
$P_{1}P_{2}$) a path obtained by concatenating $P_{1}$ with $P_{2}$. A vertex
$t\in V(G)$ is _reachable_ from $s\in V(G)$ if there is an $s\to t$ path in
$G$.

##### Planar graph toolbox.

An _$r$ -division_ [Fre87] $\mathcal{R}$ of a planar graph, for $r\in[1,n]$,
is a decomposition of the graph into a union of $O(n/r)$ pieces $P$, each of
size $O(r)$ and with $O(\sqrt{r})$ boundary vertices (denoted $\partial{P}$),
i.e., vertices shared with some other piece of $\mathcal{R}$. We denote by
$\partial{\mathcal{R}}$ the set $\bigcup_{P\in\mathcal{R}}\partial{P}$. If
additionally $G$ is plane-embedded, all pieces are connected, and the boundary
vertices of each piece $P$ of the $r$-division $\mathcal{R}$ are distributed
among $O(1)$ faces of $P$ that contain the vertices from $\partial{P}$
_exclusively_ (also called holes of $P$), we call $\mathcal{R}$ an _$r$
-division with few holes_. [KMS13] showed that an $r$-division with few holes
of a triangulated graph can be computed in linear time.

##### Fully dynamic $r$-divisions.

Many dynamic algorithms for planar graphs maintain $r$-divisions and useful
piecewise auxiliary data structures under dynamic updates. Let us slightly
generalize the definition of an $r$-division with few holes to non-planar
graphs by dropping the requirement that $G$ as a whole is planar but retaining
all the other requirements (in particular, the individual pieces are plane-
embedded).

######  Theorem 2.1.

[CK22, KS98, Sub93] Let $G=(V,E)$ be a planar graph that undergoes edge
deletions and edge insertions (assumed to preserve the planarity of $G$). Let
$r\in[1,n]$.

There is a data structure maintaining an $r$-division with few holes
$\mathcal{R}$ of some $G^{+}$, where $G^{+}$ can be obtained from $G$ by
adding edges777Note that $G^{+}$ need not be planar., such that each piece
$P\in\mathcal{R}$ is accompanied with some auxiliary data structures that can
be constructed in $T(r)$ time given $P$ and use $S(r)$ space.

The data structure uses $O\left(n+\frac{n}{r}\cdot S(r)\right)$ space and can
be initialized in $O\left(n+\frac{n}{r}\cdot T(r)\right)$ time. After each
edge insertion/deletion, it can be updated in $O(r+T(r))$ _worst-case_ time.

##  3 Fully dynamic SC data structure

To illustrate the general approach and introduce some of the concepts used for
obtaining Theorem 1.1, in this section we first prove Lemma 1.2. That is, we
show that the information whether a planar graph $G$ is strongly connected can
be maintained in $\widetilde{O}(n^{2/3})$ time per update.

We build upon the following general template used previously for designing
fully dynamic data structures supporting reachability, strong connectivity,
and shortest paths queries in planar graphs, e.g., [Sub93, KS98, FR06, CK22,
KMNS17]. As a base, we will maintain dynamically an $r$-division with few
holes $\mathcal{R}$ of $G$ using Theorem 2.1 with auxiliary piecewise data
structures to be fixed later. Intuitively, as long as the piecewise data
structures are powerful enough to allow recomputing the requested graph
property (e.g., strong connectivity, shortest path between a fixed
source/target pair) while spending $r^{1-\epsilon}$ time per piece, for some
choice of $r$ we get a sublinear update bound of
$\widetilde{O}(n/r^{\epsilon}+r+T(r))$. For example, if $T(r)=O(r^{9.9})$ and
$\epsilon=0.1$, for $r=n^{0.1}$ we get $\widetilde{O}(n^{0.99})$ worst-case
update time bound.

##### Reachability certificates.

[Sub93] described _reachability certificates_ that sparsify reachability
between a subset of vertices lying on $O(1)$ faces of a plane digraph $G$ into
a (non-necessarily planar) digraph of size near-linear in the size of the
subset in question. Formally, we have the following.

######  Lemma 3.1 ([Sub93]).

Let $H$ be a plane digraph with a distinguished set $\partial{H}\subseteq
V(H)$ lying on some $O(1)$ faces of $H$. There exists a directed graph
$X_{H}$, where $\partial{H}\subseteq V(X_{H})$, of size
$\widetilde{O}(|\partial{H}|)$ satisfying the following property: for any
$u,v\in\partial{H}$, a path $u\to v$ exists in $H$ if and only if there exists
a $u\to v$ path in $X_{H}$. The graph $X_{H}$ can be computed in
$\widetilde{O}(|H|)$ time.

######  Remark 3.2.

For Lemma 3.1 to hold, it is enough that $\partial{H}$ lies on $O(1)$ Jordan
curves in the plane, each of them having the embedding of $H$ entirely (but
not strictly) on one side of the curve. In particular, it is enough that
$\partial{H}$ lies on $O(1)$ faces of some plane supergraph $H^{\prime}$ with
$H\subseteq H^{\prime}$.

Roughly speaking, [Sub93] uses reachability certificates as auxiliary data
structures in Theorem 2.1 in order to obtain a fully dynamic reachability data
structure. Crucially, the union of the piecewise certificates preserves
pairwise reachability between the boundary vertices $\partial{\mathcal{R}}$,
or more formally (see e.g. [CK22] for a proof):

######  Lemma 3.3.

For any $u,v\in\partial{\mathcal{R}}$, $u$ can reach $v$ in $G$ if and only if
$u$ can reach $v$ in $X=\bigcup_{P\in\mathcal{R}}X_{P}$.

##### Strong connectivity data structure.

The union of certificates $X$ preserves reachability, and thus strong
connectivity between the vertices
$\partial{\mathcal{R}}:=\bigcup_{P\in\mathcal{R}}\partial{P}$. As a result, if
$G$ is strongly connected, then so is $\partial{\mathcal{R}}$ in $X$. But the
reverse implication might not hold. It turns out that for connected graphs, to
have an equivalence, it is enough to additionally maintain, for each piece
$P$, whether $P$ is strongly connected conditioned on whether $\partial{P}$ is
strongly connected in $G$.

In the following, we give a formal description of the data structure. As
already said, the data structure maintains a dynamic $r$-division
$\mathcal{R}^{+}$ of a supergraph $G^{+}$ of $G$ (i.e., the input graph), as
given by Theorem 2.1. Since $G\subseteq G^{+}$, the pieces $\\{P^{+}\cap
G:P^{+}\in\mathcal{R}^{+}\\}$ induce an $r$-division $\mathcal{R}$ of $G$;
however, a piece $P\in\mathcal{R}$ is not necessarily connected and
$\partial{P}$ not necessarily lie on $O(1)$ faces of $P$, so $\mathcal{R}$ is
not technically an $r$-division with few holes. Nevertheless, $\partial{P}$
still lies on $O(1)$ faces of a connected plane supergraph $P^{+}$ of $P$ that
do not contain vertices outside $\partial{P}$. Consequently, by Remark 3.2, we
can still use Lemma 3.1 to construct a sparse reachability certificate for the
piece $P\in\mathcal{R}$. For obtaining Lemma 1.2, we do not require anything
besides that, so for simplicity and wlog. we can assume we work with
$\mathcal{R}$ instead of $\mathcal{R}^{+}$.

While $\mathcal{R}$ evolves, each piece $P$ is accompanied with a reachability
certificate $X_{P}$ of Lemma 3.1. Note that since $|\partial{P}|=O(\sqrt{r})$,
$X_{P}$ has size $\widetilde{O}(\sqrt{r})$ and can be constructed in
$\widetilde{O}(r)$ time. Moreover, for each $P$, let $C_{\partial{P}}$ be a
directed simple cycle on the vertices $\partial{P}$. We additionally store the
(1-bit) information whether the graph $P\cup C_{\partial{P}}$ is strongly
connected. Clearly, this can be computed in $O(|P|)=O(r)$ time. All the
accompanying data structures of a piece $P\in\mathcal{R}$ can be thus
constructed in $\widetilde{O}(r)$ time. Therefore, by Theorem 2.1, they are
maintained in $\widetilde{O}(r)$ time per update.

Finally, in a separate data structure, we maintain whether $G$ is connected
(in the undirected sense). This can be maintained within $n^{o(1)}$ worst-case
update time deterministically even in general graphs [GRST21]; in our case,
also a less involved data structure such as [Fre85] would suffice.

After $\mathcal{R}$ and the accompanying data structures are updated, strong
connectivity of $G$ can be verified as follows. First of all, the union $X$ of
all $X_{P}$, $P\in\mathcal{R}$, is formed. Note that we can test whether the
vertices $\partial{\mathcal{R}}$ are strongly connected in $X$ in
$O(|X|)=\widetilde{O}(n/\sqrt{r})$ time by computing the strongly connected
components $\mathcal{S}_{X}$ of $X$ using any classical linear time algorithm.
If $G$ is not connected, or $\partial{\mathcal{R}}$ is not strongly connected
in $X$, we declare $G$ not strongly connected. If, on the other hand,
$\partial{\mathcal{R}}$ is strongly connected in $X$, we simply check whether
$P\cup C_{\partial{P}}$ is strongly connected for each $P\in\mathcal{R}$ and
if so, declare $G$ strongly connected. This takes $O(n/r)$ time. Thus, testing
strong connectivity takes $\widetilde{O}(n/\sqrt{r})$ time. The following
lemma establishes the correctness.

######  Lemma 3.4.

$G$ is strongly connected if and only if $G$ is connected, the vertices
$\partial{\mathcal{R}}$ are strongly connected in $X$, and for all
$P\in\mathcal{R}$, $P\cup C_{\partial{P}}$ is strongly connected.

###### Proof.

First suppose that $G$ is strongly connected. Then, $G$ is clearly connected.
Moreover, by Lemma 3.3, $\partial{\mathcal{R}}$ is strongly connected in $X$.
For contradiction, suppose that for some $P\in\mathcal{R}$ and $u,v\in V(P)$,
$u$ cannot reach $v$ in $P\cup C_{\partial{P}}$. By strong connectivity of
$G$, there exists some path $Q=u\to v$ in $G$. Since $u$ cannot reach $v$ in
$P$, $Q$ is not fully contained in $P$. As a result, $Q$ can be expressed as
$Q_{1}\cdot R\cdot Q_{2}$, where $Q_{1}=u\to a,Q_{2}=b\to v$ are fully
contained in $P$, and $a,b\in\partial{P}$. But there is a path $Z=a\to b$ in
$C_{\partial{P}}$, so there is a $u\to v$ path $Q_{1}\cdot Z\cdot Q_{2}$ in
$P\cup C_{\partial{P}}$, a contradiction.

Now consider the ’’$\impliedby$‘‘ direction. Suppose $G$ is connected, the
vertices $\partial{\mathcal{R}}$ are strongly connected in $X$, and for all
$P\in\mathcal{R}$, $P\cup C_{\partial{P}}$ is strongly connected. By Lemma
3.3, $\partial{\mathcal{R}}$ is strongly connected in $G$. Consider any
$P\in\mathcal{R}$ and let $x,y\in V(P)$. We first prove that there exists a
path $x\to y$ in $G$. Indeed, if an $x\to y$ path exists in $P$, it also
exists in $G$. Otherwise, since $P\cup C_{\partial{P}}$ is strongly connected,
there exists a path $Q=x\to y$ in $P\cup C_{\partial{P}}$ that can be
expressed as $Q_{1}\cdot R\cdot Q_{2}$, where $Q_{1}=x\to a$ and $Q_{2}=b\to
y$ are fully contained in $P$ and $a,b\in\partial{P}$. But since
$a,b\in\partial{\mathcal{R}}$, by strong connectivity of
$\partial{\mathcal{R}}$, there exists a path $R^{\prime}=a\to b$ in $G$. Since
$Q_{1},Q_{2}\subseteq G$, $Q_{1}\cdot R^{\prime}\cdot Q_{2}$ is an $x\to y$
path in $G$.

Now take arbitrary $u,v\in V(G)$. If there exists a piece in $\mathcal{R}$
containing both $u$ and $v$, then we have already proved that there exists a
path $u\to v$ in $G$. Otherwise, let $P_{u},P_{v}$, $P_{u}\neq P_{v}$, be some
pieces of $\mathcal{R}$ containing $u,v$, respectively. We have $P_{u}\neq G$
and $P_{v}\neq G$. Since $G$ is connected, $P_{u}$ has at least one boundary
vertex $a\in\partial{P_{u}}$. Similarly, $P_{v}$ has at least one boundary
vertex $b\in\partial{P_{v}}$. We have proved that there exist paths $u\to a$
and $b\to v$ in $G$. But also $a,b\in\partial{\mathcal{R}}$, so by the strong
connectivity of $\partial{\mathcal{R}}$, there exists a path $a\to b$ in $G$
as well. We conclude that there exists a path $u\to v$ in $G$. Since $u,v$
were arbitrary, $G$ is indeed strongly connected. ∎

The worst-case update time of the data structure is
$\widetilde{O}(r+n/\sqrt{r})+n^{o(1)}$. By setting $r=n^{2/3}$, we obtain the
following. See 1.2

##  4 Dynamic strongly connected components

The approach we take for maintaining strong connectivity in planar graphs does
not easily generalize even to dynamic SCCs counting. This is the case for the
following reason. Even if the piece $P$ is fixed (static), there can be
possibly an exponential number of different assignments of the vertices
$\partial{P}$ to the SCCs in $G$ (when the other pieces are subject to
changes), whereas for dynamic SC, a non-trivial situation arises only when all
of $\partial{P}$ lies within a single SCC. In order to achieve sublinear
update time, for any assignment we need to be able to count the SCCs fully
contained in $P$ in time sublinear in $r$ after preprocessing $P$ in only
_polynomial_ (and not exponential) time.

The following notion will be crucial for all our developments.

######  Definition 4.1.

Let $P\in\mathcal{R}$, and let $A\subseteq\partial{P}$. A _path net_
$\Pi_{P}(A)$ induced by $A$ is the set of vertices of $P$ that lie on some
directed path in $P$ connecting some two elements of $A$.

In other words, the path net $\Pi_{P}(A)$ contains vertices $v\in V(P)$ such
that $v$ can reach $A$ and can be reached from $A$ in $P$. We call a path net
$\Pi_{P}(A)$ _closed_ if $A=\Pi_{P}(A)\cap\partial{P}$, that is, there are no
boundary vertices of $P$ outside $A$ that can reach and can be reached from
$A$.

The following key lemma relates a piece‘s path net to the SCCs of $G$.

######  Lemma 4.2.

Let $S$ be an SCC of $G$ containing at least one boundary vertex of $P$, i.e.,
$S\cap\partial{P}\neq\emptyset$. Then the path net $\Pi_{P}(S\cap\partial{P})$
is closed and equals $S\cap V(P)$.

###### Proof.

Let us first argue that $\Pi_{P}(S\cap\partial{P})$ is closed. If it was not,
there would exist $b\in\partial{P}\setminus S$ such that there exist paths
$b\to(S\cap\partial{P})$ and $(S\cap\partial{P})\to b$ in $P$. It follows that
$b$ can reach and be reached from $S$ in $G$, i.e., $b$ is strongly connected
with $S$. Hence, $b\in S$, a contradiction.

Let $v\in\Pi_{P}(S\cap\partial{P})$. Since $v$ can reach and can be reached
from $S\cap\partial{P}$ in $P$, then it is indeed strongly connected with $S$
in $G$, since the vertices $S$ are strongly connected in $G$. So $v\in S\cap
V(P)$.

Now let $v\in S\cap V(P)$. Pick any $b\in S\cap\partial{P}$ (possibly $b=v$ if
$v\in\partial{P}$). There exists paths $R=v\to b$ and $Q=b\to v$ in $G$. Note
that $R$ has some prefix $R_{1}=v\to a$ that is fully contained in $P$ and
$a\in\partial{P}$. Similarly, $Q$ has a suffix $Q_{1}=c\to v$ that is fully
contained in $P$ and $c\in\partial{P}$. Since there exists paths $v\to a$,
$a\to b$, $b\to c$, $c\to v$ in $G$, vertices $a,b,c$ are strongly connected
in $G$. So $a,c\in S\cap\partial{P}$. The paths $R_{1},Q_{1}$ certify that $v$
can be reached from and can reach $S\cap\partial{P}$ in $P$. Therefore,
$v\in\Pi_{P}(S\cap\partial{P})$ as desired. ∎

If an SCC $S$ is as in Lemma 4.2, then since the vertices $\partial{P}$ might
be shared with other pieces of $\mathcal{R}$,
$\Pi_{P}(S\cap\partial{P})\setminus\partial{P}$ constitutes the vertices of
$S$ contained _exclusively in the piece $P$_. As there are only
$\widetilde{O}(n/\sqrt{r})$ boundary vertices through all pieces, their
affiliation to the SCCs of $G$ can be derived from the (SCCs of the)
certificate graph $X=\bigcup_{P\in\mathcal{R}}X_{P}$ (defined and maintained
as in Section 3), i.e., they may be handled efficiently separately.
Consequently, being able to efficiently aggregate labels – or report the
elements – of the sets of the form $\Pi_{P}(A)\setminus\partial{P}$ (where
$\Pi_{P}(A)$ is closed) is the key to obtaining an efficient implicit
representation of the SCCs of $G$. Our main technical contribution (Theorem
4.3) is the _path net data structure_ enabling precisely that. The data
structure requires a rather large $\widetilde{O}(r^{3})$ preprocessing time
but achieves the goal by supporting queries about $A\subseteq\partial{P}$ in
near-optimal $\widetilde{O}(|A|)$ time. Formally, we show:

######  Theorem 4.3.

Let $P\in\mathcal{R}$ and let $\alpha:V(P)\to\mathbb{R}$ be a weight function.
In $\widetilde{O}(r^{3})$ time one can construct a data structure satisfying
the following.

Given a subset $A\subseteq\partial{P}$ such that $\Pi_{P}(A)$ is closed, in
$\widetilde{O}(|A|)$ time one can:

  * •

create an _iterator_ that enables listing elements of
$\Pi_{P}(A)\setminus\partial{P}$ in $O(1)$ time per element,

  * •

aggregate weights over $\Pi_{P}(A)\setminus\partial{P}$, i.e., compute
$\sum_{v\in\Pi_{P}(A)\setminus\partial{P}}\alpha(v)$.

######  Remark 4.4.

We do not require using subtractions to compute the aggregate weights. In
fact, the data structure of Theorem 4.3 can be easily modified to aggregate
weights coming from any semigroup, e.g., one can compute the max/min weight in
$\Pi_{P}(A)\setminus\partial{P}$ within these bounds.

Our high-level strategy is to maintain the certificates and path net data
structures accompanying individual pieces along with the $r$-division. Roughly
speaking, to obtain the information about the SCCs of $G$ beyond how the
partition of $\partial{\mathcal{R}}$ into SCCs looks like, we will query the
path net data structures for each piece $P$ with the sets $A$ equal to the
SCCs of $X$ having non-empty intersection with $\partial{P}$. We prove Theorem
4.3 later on, in Section 5.

In the remaining part of the section, we explain in detail how, equipped with
Theorem 4.3, a dynamic (implicit) strongly connected components data structure
can be obtained. As in Section 3, we maintain an $r$-division $\mathcal{R}$
dynamically, and maintain sparse reachability certificates $X_{P}$ along with
the set $\mathcal{S}_{X}$ of SCCs of $X=\bigcup_{P\in\mathcal{R}}X_{P}$.
Moreover, for each $P$ we store the strongly connected components
$\mathcal{S}_{P}$ of $P$. Let $\mathcal{S}_{\partial{P}}$ be the elements of
$\mathcal{S}_{P}$ that contain a boundary vertex, and
$\mathcal{S}_{P\setminus\partial{P}}$ the elements of $\mathcal{S}_{P}$ that
do not. Clearly, we have
$\mathcal{S}_{P}=\mathcal{S}_{\partial{P}}\cup\mathcal{S}_{P\setminus\partial{P}}$
and
$\left(\bigcup\mathcal{S}_{P}\right)\cap\left(\bigcup\mathcal{S}_{P\setminus\partial{P}}\right)=\emptyset$.

For each piece $P\in\mathcal{R}$, we additionally store a path net data
structure $\mathcal{D}_{P}$ of Theorem 4.3 with an appropriately defined
weight function (to be chosen depending on the application later). Note that
for a piece $P$, all the auxiliary data structures accompanying $P$ that we
have defined can be computed in $\widetilde{O}(r^{3})$ time. We now consider
the specific goals that can be achieved this way.

##### Finding the largest SCC.

Denote by $S^{*}$ the largest SCC of $G$. To be able to identify $S^{*}$, and
e.g., compute its size, we proceed as follows. For each piece $P$, we
additionally maintain the largest SCC $S^{*}_{P}$ of $P$. The sizes of all the
SCCs of $P$, in particular the size of $S^{*}_{P}$, can be easily found and
stored after computing $\mathcal{S}_{P}$.

Note that if the largest SCC $S^{*}$ of $G$ is not contained entirely in any
individual piece $P$ (and thus is larger than
$\max_{P\in\mathcal{R}}|S^{*}_{P}|$), it has to intersect
$\partial{\mathcal{R}}$. More specifically, in this case for each piece $P$
such that $S^{*}\cap V(P)\neq\emptyset$, we have
$S^{*}\cap\partial{P}\neq\emptyset$.

Recall that by Lemma 3.3, $X=\bigcup_{P\in\mathcal{R}}X_{P}$ preserves the
strong connectivity relation on the vertices $\partial{\mathcal{R}}$.
Therefore, if $S^{*}$ intersects $\partial{\mathcal{R}}$, it has to contain
$B\cap\partial{\mathcal{R}}$ for some SCC $B$ of $X$. For any such $B$, we can
compute the size of the SCC $S_{B}$ of $G$ satisfying
$B\cap\partial{\mathcal{R}}\subseteq S_{B}$ as follows. First of all,
$|S_{B}\cap\partial{\mathcal{R}}|=|B\cap\partial{\mathcal{R}}|$ since $B$ is
an SCC of $X$. It is thus enough to compute, for all $P\in\mathcal{R}$,
$|S_{B}\cap(V(P)\setminus\partial{P})|$. Since the sets
$V(P)\setminus\partial{P}$ are pairwise disjoint across the pieces, by adding
these values, we will get the desired size $|S_{B}|$.

We have already argued that if $B\cap\partial{P}=\emptyset$, then $S_{B}\cap
V(P)=\emptyset$. If, on the other hand, $B\cap\partial{P}$ is non-empty, by
Lemma 4.2, if we use the weight function $\alpha(v)\equiv 1$ in the piecewise
data structures $\mathcal{D}_{P}$ of Theorem 4.3, we can compute
$|S_{B}\cap(V(P)\setminus\partial{P})|=\sum_{v\in\Pi_{P}(B\cap\partial{P})\setminus\partial{P}}\alpha(v)$
in $\widetilde{O}(|B\cap\partial{P}|)$ time using the input set
$A:=B\cap\partial{P}$. We conclude that the sizes $S_{B}$ for all
$B\in\mathcal{S}_{X}$ can be computed in time

$\widetilde{O}\left(\sum_{B\in\mathcal{S}_{X}}\sum_{\begin{subarray}{c}P\in\mathcal{R}\\\
B\cap\partial{P}\neq\emptyset\end{subarray}}|B\cap\partial{P}|\right)=\widetilde{O}\left(\sum_{P\in\mathcal{R}}\sum_{\begin{subarray}{c}B\in\mathcal{S}_{X}\\\
B\cap\partial{P}\neq\emptyset\end{subarray}}|B\cap\partial{P}|\right)=\widetilde{O}\left(\sum_{P\in\mathcal{R}}|\partial{P}|\right)=\widetilde{O}(n/\sqrt{r}).$
(1)

Finally, $S^{*}$ is either equal to the largest $S_{B}$ for
$B\in\mathcal{S}_{X}$, or the largest $S^{*}_{P}$ (through $P\in\mathcal{R}$).
The latter is the case if
$\max_{B\in\mathcal{S}_{X}}|S_{B}|<\max_{P\in\mathcal{R}}|S^{*}_{P}|$. Which
case we fall into is easily decided once all the $O(n/\sqrt{r})$ sizes
$|S_{B}|$ are computed.

##### Accessing the SCC of a specified vertex.

Suppose first that we know the SCC $S_{v}$ of $G$ containing a query vertex
$v$, and additionally whether $S_{v}$ intersects $\partial{\mathcal{R}}$. If
$S_{v}\cap\partial{\mathcal{R}}=\emptyset$, then $v$ is a vertex of a unique
piece $P$, and $S_{v}\in\mathcal{S}_{P\setminus\partial{P}}$. In this case, we
can clearly compute the size of $S_{v}$ and report the elements of $S_{v}$ in
$O(1)$ time since $S_{v}\in\mathcal{S}_{P}$ is stored explicitly.

Otherwise, if $S_{v}\cap\partial{\mathcal{R}}\neq\emptyset$, we reuse the
information that we have computed for finding the largest SCC. We have already
described how to compute the sizes of all the SCCs $S$ of $G$ intersecting
$\partial{\mathcal{R}}$ (in particular $S_{v}$) along with these respective
intersections in $\widetilde{O}(n/\sqrt{r})$ time upon update. Moreover, for
all $P\in\mathcal{R}$ we have computed $|S\cap(V(P)\setminus\partial{P})|$
using the data structure $\mathcal{D}_{P}$ of Theorem 4.3. As a result, we can
store, for each such $S$, a subset $L(S)\subseteq\mathcal{R}$ of pieces $P$
such that $S\cap(V(P)\setminus\partial{P})\neq\emptyset$. Recall that for all
$P\in L(S)$, we can also use $\mathcal{D}_{P}$ to create an iterator for
reporting the elements of $S\cap(V(P)\setminus\partial{P})$ in $O(1)$ time per
element. So, in order to efficiently report elements of any such $S$, we first
report the vertices of $S\cap\partial{\mathcal{R}}$, and then the elements of
each $S\cap(V(P)\setminus\partial{P})$ for subsequent pieces $P\in L(S)$.
Indeed, one needs only $O(1)$ worst-case time to find each subsequent vertex
of $S$.

Finally, we are left with the task of of finding the SCC $S_{v}$ of a query
vertex $v\in V$. It is not clear how to leverage path net data structures for
that in the case when $S_{v}$ intersects $\partial{\mathcal{R}}$. Instead, we
use the data structure of [CK22] in a black-box way. That data structure
handles fully dynamic edge updates in $\widetilde{O}(n^{4/5})$ worst-case
time, and provides $O(\log^{2}{n})$ worst-case time access to consistent (for
queries issued between any two subsequent updates) SCC identifiers of
individual vertices888The query time of that data structure can be easily
reduced to $O(\log{n}\cdot\log\log{n})$ without affecting the
$\widetilde{O}(n^{4/5})$ update bound if one simply replaces the classical
MSSP data structure [Kle05] used internally for performing point location
queries in additively weighted Voronoi diagrams [GMWW18] with the MSSP data
structure of [LP21].. Using [CK22], after every update we find the identifiers
$I$ of the SCCs of vertices $\partial{\mathcal{R}}$ in $G$ in
$\widetilde{O}(n/\sqrt{r})$ time. Now, to find the SCC of $v$ upon query, we
find the identifier $i_{v}$ of the SCC containing $v$ in $O(\log^{2}{n})$
time. If $i_{v}\in I$ (which can be tested in $O(\log{n})$ time), we obtain
that $v$ is in an SCC of $G$ intersecting $\partial{\mathcal{R}}$ and some
vertex $b_{v}$ from the intersection. $b_{v}$ can be in turn used to access
$L(S_{v})$ and thus enable reporting the elements of $S_{v}$. Otherwise, if
$i_{v}\notin I$, $S\cap\partial{\mathcal{R}}=\emptyset$ and thus $S$ equals
the unique SCC from $S_{P\setminus\partial{P}}$ containing $v$ in the unique
piece $P$ containing $v$.

##### Counting strongly connected components.

Let us separately count SCCs $\mathcal{S}_{\partial{\mathcal{R}}}$ that
intersect $\partial{\mathcal{R}}$ and those that do not. The former can be
counted in $\widetilde{O}(n/\sqrt{r})$ time by counting the SCCs of $X$ that
intersect $\partial{\mathcal{R}}$ (that we maintain). The latter can be
computed as follows. Consider the sum
$\Phi=\sum_{P\in\mathcal{R}}|\mathcal{S}_{P\setminus\partial{P}}|$. If we
wanted the sum $\Phi$ to count the SCCs not intersecting
$\partial{\mathcal{R}}$, then an SCC $S\in\mathcal{S}_{P\setminus\partial{P}}$
contributes to the sum unnecessarily precisely when $S$ is not an SCC of $G$.
To see that, note that if an SCC $S$ of $P$ is not an SCC of $G$, it has to be
a part of another SCC $S^{\prime}$ of $G$ that also contains vertices of other
pieces, i.e., $S^{\prime}$ intersects $\partial{\mathcal{R}}$. From Lemma 4.2,
we conclude:

######  Corollary 4.5.

An SCC $S\in\mathcal{S}_{P\setminus\partial{P}}$ is not an SCC of $G$ iff
there exists (precisely one) SCC $B$ of $X$ such that
$S\subseteq\Pi_{P}(B\cap\partial{P})$ (or equivalently, such that
$S\cap\Pi_{P}(B\cap\partial{P})\neq\emptyset$).

As a result, we can count the number of SCCs in $G$ that do not intersect
$\partial{\mathcal{R}}$ by subtracting from $\Phi$, for each
$P\in\mathcal{R}$, and each $B\in\mathcal{S}_{X}$ the number $c_{P,B}$ of SCCs
in $\mathcal{S}_{P\setminus\partial{P}}$ that intersect
$\Pi_{P}(B\cap\partial{P})$. To this end, we can use the data structure
$\mathcal{D}_{P}$ of Theorem 4.3 built upon $P$ (and maintained as described
before) with a weight function $\alpha$ on $V(P)$ assigning $1$ to an
arbitrary single vertex $v_{S}$ of each SCC
$S\in\mathcal{S}_{P\setminus\partial{P}}$, and $0$ to all other vertices. By
Corollary 4.5, with such a weight function,
$c_{P,B}=\sum_{v\in\Pi_{P}(B\cap\partial{P})\setminus\partial{P}}\alpha(v)$
can be computed in $\widetilde{O}(|B\cap\partial{P}|)$ time using
$\mathcal{D}_{P}$. Consequently, similarly as in (1), over all
$B\in\mathcal{S}_{X}$, and $P\in\mathcal{R}$, computing all the values
$c_{P,B}$ will take $\widetilde{O}(n/\sqrt{r})$ time. As mentioned before, the
SCC count is obtained by subtracting those from $\Phi$ and adding the result
to the count of $\mathcal{S}_{\partial{\mathcal{R}}}$.

Depending on the application, the worst-case update time of the data structure
is $\widetilde{O}(n/\sqrt{r}+r^{3})$ or
$\widetilde{O}(n/\sqrt{r}+r^{3}+n^{4/5})$. The bound is optimized for
$r=n^{2/7}$ and this yields the following. See 1.1

##  5 The path net data structure

This section is devoted to describing the below key component of our dynamic
SCCs data structure. See 4.3

###  5.1 Overview

[CK22] showed that for any SCC $S$ of $G$, $V(P)\cap S$ forms an intersection
of two cells coming from two carefully prepared additively weighted Voronoi
diagrams on $P$ with sites $\partial{P}$. As a result, they could use Voronoi
diagram point location mechanism [GMWW18, LP21] for testing in
$O(\operatorname{polylog}{n})$ time whether a query vertex lies in such an
intersection. If we tried to follow this approach, we would need to be able to
aggregate/report vertices in such intersections of cells coming from two
seemingly unrelated Voronoi diagrams. This is very different from just testing
membership, and it is not clear whether this can be done efficiently.

Instead, in order to prove Theorem 4.3, we take a more direct approach. As is
done typically, we first consider the situation when $A$ lies on a single face
of $P$. In the single-hole case, the first step is to reduce to the case when
the input piece $P$ is acyclic; note that if a vertex lies in the path net
$\Pi_{P}(A)$, its entire SCC in $P$ does. Acyclicity and appropriate
perturbation [EFL18] allows us to pick a collection of paths $\pi_{u,v}$, for
all $u,v\in\partial{P}$, such that every two paths in the collection are
either disjoint or their intersection forms a single subpath of both. This
property makes the paths $\pi_{u,v}$ particularly convenient to use for
cutting the piece $P$ into smaller non-overlapping parts.

More specifically, the paths $\pi_{u,v}$ are used to partition – using a
polygon triangulation-like procedure – a queried net $\Pi_{P}(A)$ into regions
in the plane with vertices $B\subseteq A$ bounded by either fragments of the
face of $P$ containing $\partial{P}$ or some paths $\pi_{u,v}$ for $u,v\in B$
(so-called _base instances_). A base instance has a very special structure
guaranteeing that for a given vertex $v\in V(P)\setminus\partial{P}$, there
are _only $O(1)$ pairs_ $s,t\in B$ such that an $s\to v\to t$ path exists in
$P$. At the end, this crucial property can be used to reduce a base instance
query $B$ even further to looking up $\widetilde{O}(|B|)$ preprocessed answers
for base instances with at most $5$ vertices from $\partial{P}$, of which
there are at most $\widetilde{O}(|\partial{P}|^{5})=\widetilde{O}(r^{5/2})$.
The precomputation of small base instances can be done in
$\widetilde{O}(r^{3})$ time.

For efficiently implementing the polygon triangulation-like partition
procedure – which repeatedly cuts off base instances from the ’’core‘‘ part of
the problem – we develop a dynamic data structure for existential reachability
queries on a single face of a plane digraph (Lemma 5.3, proved in Section
5.8). To this end, we leverage the single-face reachability characterization
of [IKŁS17].

As the final step, we show a reduction from the case when $A$ can lie on $k$
faces on $P$ to the case when $A$ lies on $k-1$ faces. The reduction – which
eventually reduces the problem to the single-hole case – can blow up the
piece‘s size by a constant factor. However, since there are only $O(1)$ holes
initially, the general case can still be solved only a constant factor slower
than the single-hole case.

###  5.2 Reducing to the acyclic case

Recall that $P$ is a piece of an $r$-division with few holes $\mathcal{R}$ and
thus has size $O(r)$. Moreover, $\partial{P}$ lies on $O(1)$ faces (_holes_)
of some supergraph $P^{+}$ of $P$ and $|\partial{P}|=O(\sqrt{r})$. For
simplicity, we will not differentiate between the faces/holes of $P$ and
$P^{+}$. Whenever we refer to a hole $h$ of $P$, we mean a closed curve $h$ in
the plane such that whole embedding of $P$ lies weakly on a single side of
$h$, and only vertices $\partial{P}$ may lie on the curve $h$.

First of all, we compute the strongly connected components $\mathcal{S}_{P}$
of $P$. Observe that from the point of view of supported queries, all vertices
of a single SCC $S\in\mathcal{S}_{P}$ are treated exactly the same: when a
single vertex $v\in S\setminus\partial{P}$ is reported (or its weight
$\alpha(v)$ is aggregated), all other vertices from $S\setminus\partial{P}$
are as well. For each $S\in\mathcal{S}_{P}$ we precompute the aggregate weight
$\alpha(S)=\sum_{v\in S\setminus\partial{P}}\alpha(v)$ in $O(r)$ time. We then
contract each strongly connected component $S\in\mathcal{S}_{P}$ into a single
vertex $v_{S}$. Crucially, since each subgraph $P[S]$ is connected in the
undirected sense, contractions can be performed in an embedding preserving way
(via a sequence of single-edge contractions), so that:

  * •

The obtained graph $P^{\prime}$ is acyclic.

  * •

The vertices
$\partial{P^{\prime}}:=\\{v_{S}:S\in\mathcal{S}_{P},S\cap\partial{P}\neq\emptyset\\}$
lie on $O(1)$ faces of (a supergraph of) $P^{\prime}$.

Indeed, to see the latter property, label each $b\in\partial{P}$ initially
each with hole that $b$ lies on and make non-boundary vertices unlabeled. When
the vertices merge, label the resulting vertex using one of the involved
vertices‘ labels, if any of them has one. At the end there will be still
$O(1)$ labels, each vertex of $\partial{P^{\prime}}$ will have one of these
labels, and for each label, all the vertices holding that label will be
incident to a single face of $P^{\prime}$. Clearly, $|P^{\prime}|=O(r)$ and
$|\partial{P^{\prime}}|=O(\sqrt{r})$.

######  Lemma 5.1.

Suppose a data structure $\mathcal{D}^{\prime}$ of Theorem 4.3 is built for
the acyclic graph $P^{\prime}$ with the weight function
$\alpha^{\prime}(v_{S}):=\alpha(S)=\sum_{v\in
S\setminus\partial{P}}\alpha(v)$. Then, a query $A\subseteq\partial{P}$ from
Theorem 4.3 can be reduced, in $O(|A|)$ time, to a query about
$A^{\prime}=\\{v_{S}:S\in\mathcal{S}_{P},S\cap A\neq\emptyset\\}$ issued to
$\mathcal{D}^{\prime}$.

###### Proof.

By the assumption that $\Pi_{P}(A)$ is closed, we have that $\Pi_{P}(A)$
contains only such $S\in\mathcal{S}_{P}$ that $S\cap\partial{P}\subseteq A$.
If the set $\Pi_{P^{\prime}}(A^{\prime})$ contained some
$v_{R}\in\partial{P^{\prime}}\setminus A^{\prime}$, then in the graph $P$ a
vertex from $R\cap(\partial{P}\setminus A)$ could reach and could be reached
from $A$, which would contradict $\Pi_{P}(A)\cap\partial{P}=A$. As a result,
$A^{\prime}$ is indeed a valid query parameter to the data structure
$\mathcal{D}^{\prime}$ and in
$\widetilde{O}(|A^{\prime}|)\leq\widetilde{O}(|A|)$ time we can gain reporting
access to $\Pi_{P^{\prime}}(A^{\prime})\setminus\partial{P^{\prime}}$ or
aggregate the weights of
$\Pi_{P^{\prime}}(A^{\prime})\setminus\partial{P^{\prime}}$. Observe that any
vertex $v_{S}\in\Pi_{P^{\prime}}(A^{\prime})\setminus\partial{P^{\prime}}$
corresponds to a subset $S\subseteq\Pi_{P}(A)\setminus\partial{P}$. These
subsets $S$, being strongly connected components of $P$, are clearly pairwise
disjoint. So the reporting procedure, when $\mathcal{D^{\prime}}$ reports
$v_{S}$, can simply report the individual vertices of $S$ one by one.
Moreover, the weight $\alpha(v_{S})$ equals the aggregate weight $\sum_{v\in
S}\alpha(v)$. It is easy to see that this way, using $\mathcal{D^{\prime}}$ we
can actually efficiently report/aggregate all the vertices of
$(\Pi_{P}(A)\setminus\partial{P})\cap\left(\bigcup\\{S:v_{S}\in\Pi_{P^{\prime}}(A^{\prime})\setminus\partial{P^{\prime}}\\}\right)$,
or, in other words, the vertices of $\Pi_{P}(A)\setminus\partial{P}$ that are
not strongly connected to a boundary vertex of $P$. However, some vertices
from $\Pi_{P}(A)\setminus\partial{P}$ are not necessarily in
$\bigcup\\{S:v_{S}\in\Pi_{P^{\prime}}(A^{\prime})\setminus\partial{P^{\prime}}\\}$.
But these are precisely the non-boundary vertices of $P$ that are strongly
connected to some vertex of $A$ in $P$. As a result, we can handle these
remaining vertices by iterating over the $O(|A|)$ SCCs of $P$ that intersect
$A$. ∎

In the following we will assume that $P$ is an acyclic graph. We will no
longer need the assumption $\Pi_{P}(A)\cap\partial{P}=A$; this was only needed
for the efficient reduction to the acyclic case. Consequently, we will design
a data structure with query time $\widetilde{O}(|A|)$ even if
$A\subsetneq\Pi_{P}(A)\cap\partial{P}$.

In the remaining part of this section, we assume we only want to handle
queries where the query set $A$ lies on a _single hole_ $h$ of an acyclic
piece $P$. We present the reduction of the general case to the single-hole
case in Section 5.7. Our strategy for the single-hole case will be to
efficiently break the problem into subproblems for which we have the answer
precomputed.

###  5.3 Picking non-crossing paths.

We first fix, for any $u,v\in V(P)$ such that $u$ can reach $v$, one
particular $u\to v$ path $\pi_{u,v}\subseteq P$. We apply the perturbation
scheme of [EFL18] to $P$, so that the shortest paths in $P$ become unique. For
any $u,v\in V(P)$ such that $u$ can reach $v$ in $P$, we define $\pi_{u,v}$ to
be the unique shortest $u\to v$ path in $P$. Note that each $\pi_{u,v}$ is a
simple path in $P$. We have the following crucial property.

######  Lemma 5.2.

Let $u,v,x,y\in V(P)$ be such that $u$ can reach $v$ and $x$ can reach $y$ in
$P$. If $V(\pi_{u,v})\cap V(\pi_{x,y})\neq\emptyset$, then $\pi_{u,v}$ and
$\pi_{x,y}$ share a single (possibly zero-edge) subpath.

###### Proof.

Let $a$ ($b$) be the first (last, resp.) vertex on $\pi_{u,v}$ that is also a
vertex of $\pi_{x,y}$. $\pi_{u,v}$ can be expressed as $Q_{1}\cdot T\cdot
Q_{2}$, where $T=a\to b$. Moreover, $V(\pi_{u,v})\cap V(\pi_{x,y})\subseteq
V(T)$. If $a\neq b$, the vertex $b$ cannot appear before $a$ on $\pi_{x,y}$,
because then $a$ and $b$ would lie on a cycle in $P$, contradicting acyclicity
of $P$. As a result, $\pi_{x,y}$ has an $a\to b$ subpath as well. Since
shortest paths in $P$ are unique and shortest paths have optimal substructure,
the $a\to b$ subpath of $\pi_{x,y}$ equals $T$. So, $\pi_{x,y}$ can be
expressed as $R_{1}\cdot T\cdot R_{2}$. Since $\pi_{x,y}$ is simple, and
$V(\pi_{u,v})\cap V(\pi_{x,y})\subseteq V(T)$, we indeed have
$\pi_{u,v}\cap\pi_{x,y}=T$. ∎

Observe that since $P$ is a DAG, for $u,v\in V(P)$, $u\neq v$, $\pi_{u,v}$ and
$\pi_{v,u}$ cannot both exist. When one of them exists, we will sometimes
write $\pi_{\\{u,v\\}}$ to denote the one that exists.

###  5.4 Generalization

Before we proceed, we need to state our problem in a more general way that
will enable decomposition into smaller subproblems of similar kind. Let us
first fix a counterclockwise order of $V(h)$, as follows. Let
$u_{1},e_{1},u_{2},e_{2},\ldots,u_{r},e_{r}$ be the sequence of vertices and
edges on a counterclockwise bounding walk of $h$ with an arbitrary starting
point. The encountered vertices $u_{i}$ might not be all distinct since $h$
can be a non-simple face in general. The order $\prec_{h}$ of $V(h)$ that we
use is obtained by removing duplicate vertices from the sequence in an
arbitrary way, i.e., for each $v\in V(h)$ we pick one index $i_{v}$ such that
$u_{i_{v}}=v$. If $x,y\in V(h)$ and $i_{x}<i_{y}$, then we define $C_{x,y}$ to
be the curve $e_{i_{x}}e_{i_{x}+1}\ldots e_{i_{y}-1}$. Otherwise, if
$i_{x}>i_{y}$, then $C_{x,y}=e_{i_{x}}e_{i_{x}+1}\ldots e_{r}e_{1}e_{2}\ldots
e_{i_{y}-1}$. If $h$ is simple, then $C_{x,y}$ is a simple curve. However, in
general, $C_{x,y}$ can be self-touching but it does not cross itself.

Suppose $B\subseteq\partial{P}\cap V(h)$ is given ordered by $\prec_{h}$.
Moreover, for each pair of neighboring (i.e., appearing consecutively in the
_cyclic_ order of $B$ given by $\prec_{h}$) vertices $x,y$ of $B$, a curve
$\Phi_{x,y}$ connecting $x$ to $y$ is given. The curve $\Phi_{x,y}$ equals
either $\pi_{\\{x,y\\}}$ or $C_{x,y}$. Let $\Phi$ be the closed curve formed
by concatenating the subsequent curves $\Phi_{x,y}$ for all neighboring
$x,y\in B$. For brevity, we also extend the notation $\Phi_{a,b}$ to non-
neighboring vertices $a,b$ of $B$, and define $\Phi_{a,b}$ to be a
concatenation of the curves $\Phi_{x,y}$ for all neighboring pairs $(x,y)$
between $a$ and $b$ on $\Phi$. We don‘t require $\Phi$ to be a simple (Jordan)
curve; parts of it may be overlapping. Whereas $\Phi$ is allowed to be self-
touching, it does not cross itself, like e.g., the cycle bounding a non-simple
face of a plane graph. Let $P[\Phi]$ denote the region of $P$ that lies
_weakly_ inside the curve $\Phi$.

The objective of the problem $(B,\Phi)$ is to aggregate weights of (or report)
the vertices of ${\Pi_{P}(B)\setminus\partial{P}}$ that lie _strictly inside_
$\Phi$. More formally, we want to aggregate vertices $v$ that lie, at the same
time, strictly on the left side of each of the curves $\Phi_{x,y}$ (seen as a
curve directed from $x$ to $y$) where $x,y$ are neighboring elements of $B$
sorted by $\prec_{h}$.999Even more formally, assuming $P$ is embedded in such
a way that $h$ is the infinite face of a supergraph of $P$, we are interested
in the vertices lying in the intersection of the regions strictly inside
closed curves $\Phi_{x,y}\cdot C_{y,x}$ for all neighboring $x,y$ in $B$. Note
that with such a defined problem, the original goal of the query procedure can
be rephrased as $(A,h)$ since all the vertices of
$\Pi_{P}(A)\setminus\partial{P}$ indeed lie strictly inside $h$.

###  5.5 Preprocessing

##### Preprocessing for small instances and subproblems.

  * •

For any tuple $B=(b_{1},\ldots,b_{q})$ of at most $4$ vertices of
$\partial{P}$ appearing in that order in $\prec_{h}$, and any out of at most
$2^{q}=O(1)$ possible curves $\Phi$ that might constitute the problem
$(B,\Phi)$, we precompute the aggregate weight and the list of vertices in
$\Pi_{P}(B)\setminus\partial{P}$ that lie strictly inside $\Phi$. This can
clearly be done in
$\widetilde{O}(|\partial{P}|^{4}\cdot|P|)=\widetilde{O}(r^{3})$ time.

  * •

For any 5-tuple $\tau=(b_{0},\ldots,b_{4})$ ordered by $\prec_{h}$, and any
out of at most $2^{4}$ possible curves
$\Phi_{b_{i},b_{i+1}}\in\\{\pi_{\\{b_{i},b_{i+1}\\}},C_{b_{i},b_{i+1}}\\}$,
where $i\in\\{0,\ldots,3\\}$, we precompute and store the set $X_{\tau}$ of
vertices $x\in V(P)\setminus\partial{P}$ such that:

    1. 1.

$x$ lies on some path connecting $b_{1}$ and $b_{2}$ in $P$,

    2. 2.

$x$ _does not_ lie on any path connecting $b_{0}$ and $b_{1}$ in $P$,

    3. 3.

$x$ lies strictly to the left of each $\Phi_{b_{i},b_{i+1}}$ for
$i=\\{0,\ldots,3\\}$.

We also store the aggregate weight $w(X_{\tau})$. This preprocessing can be
performed in a brute-force way in
$\widetilde{O}(|\partial{P}|^{5}\cdot|P|)=\widetilde{O}(r^{7/2})$ time. It can
be also optimized fairly easily to $\widetilde{O}(r^{3})$ time and space, as
follows.

First, for every $a\in\partial{P}$, and $v\in V(P)\setminus\partial{P}$, find
the earliest vertex $z_{a,v}\in\partial{P}$ following $a$ in the order
$\prec_{h}$ such that $v$ does not lie strictly to the left of
$\pi_{\\{a,z_{a,v}\\}}$. Note that having fixed $a\in\partial{P}$, the
property of $v$ being strictly left of $\pi_{\\{a,b\\}}$ is monotonous in the
vertex $b\in\partial{P}$ following $a$. The vertices $z_{a,v}$ can be computed
in $\widetilde{O}(|\partial{P}|^{2}\cdot|P|^{2})=\widetilde{O}(r^{3})$
naively.

Having fixed $(b_{0},\ldots,b_{3})$, compute the set $X^{\prime}$ of all
vertices $x\in V(P)\setminus\partial{P}$ satisfying all the above conditions
possibly except the one that $x$ lies strictly to the left of
$\Phi_{b_{3},b_{4}}$. Computing all such $X^{\prime}$ takes
$\widetilde{O}(|\partial{P}|^{4}\cdot|P|)=\widetilde{O}(r^{3})$ time. Now, for
each of the $\widetilde{O}(r^{2})$ obtained sets $X^{\prime}$, in
$\widetilde{O}(r)$ time we sort the elements $x\in X^{\prime}$ by the value
$z_{b_{3},x}$ where $z_{b_{3},x}$ ($b_{3}\prec_{h}z_{b_{3},x}$) appearing
later in $\prec_{h}$ is considered smaller. This way, for each possible
$b_{4}\in B$, the desired set of vertices $X_{\tau}$ forms a prefix of the
vertices $X^{\prime}$: we have $x\in X_{\tau}$ iff $x\in X^{\prime}$ and
$z_{b_{3},x}$ appears later than $b_{4}$ (and after $b_{3}$) in the order
$\prec_{h}$. Storing $X^{\prime}$ sorted like that, along with the aggregate
prefix weights, allows us to aggregate/report any set $X_{\tau}$ for a 5-tuple
$\tau=(b_{0},\ldots,b_{4})$ and 4-tuple $(\Phi_{b_{i},b_{i+1}})_{i=0}^{3}$ in
$O(1)$ time after only $\widetilde{O}(r^{3})$ preprocessing.

  * •

For any $u,v\in\partial{P}$, we store the path $\pi_{\\{u,v\\}}$ itself, along
with aggregate weights of all its subpaths. This data can be computed in
$\widetilde{O}(|\partial{P}|^{2}\cdot|P|^{2})=\widetilde{O}(r^{3})$ time in a
brute-force way.

  * •

Finally, for any two pairs $(u,v),(x,y)\in\partial{P}\times\partial{P}$, we
compute the intersection of the paths $\pi_{\\{u,v\\}}$ and $\pi_{\\{x,y\\}}$.
By Lemma 5.2, that intersection is either empty or is a subpath of both these
paths. Hence, it is enough to store the two endpoints of the intersection
subpath only. The desired intersections can be found in
$\widetilde{O}(|\partial{P}|^{4}\cdot|P|)=\widetilde{O}(r^{3})$ time in a
brute-force way.

##### Existential reachability data structure.

We also build data structures $\mathcal{L},\mathcal{L}^{R}$ of the following
lemma for $P$ and $P^{R}$, respectively.

######  Lemma 5.3.

In $\widetilde{O}(r)$ time one can construct a data structure maintaining an
(initially empty) set $Z\subseteq\partial{P}\cap V(h)$ and supporting the
following operations in $O(\operatorname{polylog}{n})$ time:

  * •

insert or delete a single $b\in\partial{P}\cap V(h)$ either to or from $Z$.

  * •

for any query vertex $v\in(\partial{P}\cap V(h))\setminus Z$, find any $z\in
Z$ (if exists) that $v$ can reach in $P$.

The proof of Lemma 5.3 is deferred to Section 5.8.

###  5.6 Answering queries

We now proceed with the description of our algorithm solving the general
problem $(B,\Phi)$.

##### Base case.

Let the elements of $B=\\{b_{1},\ldots,b_{k}\\}$ be sorted according to their
order $\prec_{h}$ on $\Phi$. For convenience, identify $b_{k+l}$ with $b_{l}$
for any integer $l$.

We first consider the easier _base case_ , with the following additional
requirement:

> For any $1\leq i<j\leq k$, if $b_{i}$ can reach $b_{j}$ or can be reached
> from $b_{j}$ in $P$, then either $j=i+1$ or $(i,j)=(1,k)$.

If $k\leq 4$, we will simply return the precomputed aggregate weight, or an
iterator to a list of vertices in $\Pi_{P}(B)\setminus\partial{P}$ strictly
inside $\Phi$. So suppose $k\geq 5$. We start with the following lemma.

######  Lemma 5.4.

Let $v\in\Pi_{P}(B)\setminus\partial{P}$ lie strictly inside $\Phi$. Then:

  * •

There exists such $i$ that $v$ lies on some $b_{i}\to b_{i+1}$ or on some
$b_{i+1}\to b_{i}$ path in $P$.

  * •

Moreover, there is at most one more pair $\\{x,y\\}\subseteq B$,
$\\{x,y\\}\neq\\{b_{i},b_{i+1}\\}$ such that $v$ lies on some $x\to y$ or
$y\to x$ path in $P$, and either $\\{x,y\\}=\\{b_{i-1},b_{i}\\}$, or
$\\{x,y\\}=\\{b_{i+1},b_{i+2}\\}$.

###### Proof.

Item (1) follows easily by the additional requirement of the base case. Let
$v$ lie on some $b_{j}\to c$ path in $P$, where $c\in B$. Since $P$ is
acyclic, we have that $b_{j}\neq c$ and thus $c\in\\{b_{j-1},b_{j+1}\\}$. If
$c=b_{j+1}$, we put $i=j$ and if $c=b_{j-1}$, we put $i=j-1$.

For item (2), consider the case when $v$ lies on some $b_{i}\to b_{i+1}$; the
case when $v$ lies on a $b_{i+1}\to b_{i}$ path is symmetric. Suppose $v$ also
lies on some $x\to y$ path in $P$, where $x,y\in B$, $x\neq y$,
$\\{x,y\\}\neq\\{b_{i},b_{i+1}\\}$. Since $b_{i}$ can reach $y$ through $v$,
$y\in\\{b_{i-1},b_{i+1}\\}$ by the requirement. Similarly, since $x$ can reach
$b_{i+1}$ through $v$, $x\in\\{b_{i},b_{i+2}\\}$. We cannot have $x=b_{i+2}$
and $y=b_{i-1}$ since $b_{i+2}$ reaching $b_{i-1}$ is a contradiction with the
first base case requirement for $k\geq 5$. As a result,
$(x,y)\neq(b_{i},b_{i+1})$ implies $(x,y)=(b_{i},b_{i-1})$ or
$(x,y)=(b_{i+2},b_{i+1})$. Moreover, $v$ cannot lie on both some $b_{i}\to
b_{i-1}$ path and some $b_{i+2}\to b_{i+1}$ path, since then $b_{i+2}$ could
reach $b_{i-1}$, which is again a contradiction for $k\geq 5$. ∎

By Lemma 5.4, each $v\in\Pi_{P}(B)\setminus\partial{P}$ falls into exactly one
of the $k$ sets $Y_{i}$, for $i=1,\ldots,k$, such that $Y_{i}$ contains those
$v$ in $V(P)\setminus\partial{P}$ that lie on a path in $P$ connecting $b_{i}$
and $b_{i+1}$ (in any direction), but at the same time _do not_ lie on any
path connecting $b_{i-1}$ and $b_{i}$ in $P$ (in any direction). Indeed, if
$v$ appears only on paths connecting $b_{i}$ and $b_{i+1}$, it will be
included in $Y_{i}$. On the other hand, if $v$ appears both on paths
connecting $b_{i}$ and $b_{i+1}$ and on paths connecting $b_{i+1}$ and
$b_{i+2}$, it will be included only in $Y_{i}$, but not in $Y_{i+1}$.

######  Lemma 5.5.

Suppose $v\in Y_{i}$. Then $v$ lies strictly inside $\Phi$ if and only if $v$
lies strictly on the left side of $\Phi_{b_{i-1},b_{i}}$,
$\Phi_{b_{i},b_{i+1}}$, $\Phi_{b_{i+1},b_{i+2}}$, and
$\Phi_{b_{i+2},b_{i+3}}$.

###### Proof.

Since strictly inside $\Phi$ means strictly to the left of all
$\Phi_{b_{j},b_{j+1}}$, the ’’$\implies$‘‘ direction is trivial.

Consider the ’’$\impliedby$‘‘ direction. For contradiction, suppose $v$ does
not lie strictly inside $\Phi$. Then, for some $j\notin\\{i-1,i,i+1,i+2\\}$,
$v$ lies weakly to the right of $\Phi_{b_{j},b_{j+1}}$. Since $v\in
V(P)\setminus\partial{P}$ and the hole $h$ contains only vertices of
$\partial{P}$, this means that
$\Phi_{b_{j},b_{j+1}}=\pi_{\\{b_{j},b_{j+1}\\}}$. Since $b_{j}$ and $b_{j+1}$
are consecutive in $B$, and $i\notin\\{j,j+1\\}$, $b_{i}$ lies weakly to the
left of $\pi_{\\{b_{j},b_{j+1}\\}}$.

By $v\in Y_{i}$, the vertex $v$ lies on a path $Q$ connecting $b_{i}$ and
$b_{i+1}$ in $P$. Since $v$ and $b_{i}$ lie weakly on different sides of
$\pi_{\\{b_{j},b_{j+1}\\}}$, the path $Q$ has to cross
$\pi_{\\{b_{j},b_{j+1}\\}}$ at a vertex $w$ appearing not later than $v$ on
$Q$ (possibly $v=w$). If $Q=b_{i}\to b_{i+1}$, the existence of $w$ implies
that there exists an $s\to b_{i+1}$ path in $P$ going through $v$ such that
$s\in\\{b_{j},b_{j+1}\\}$. By $v\in Y_{i}$, this implies
$s\in\\{b_{i},b_{i+2}\\}$. As a result, $j\in\\{i-1,i,i+1,i+2\\}$, a
contradiction. Similarly, if $Q=b_{i+1}\to b_{i}$, there exists an $s\to
b_{i}$ path in $P$ going through $v$ such that $s\in\\{b_{j},b_{j+1}\\}$. But
on the other hand by $v\in Y_{i}$ we have $s=b_{i+1}$ so $j\in\\{i,i+1\\}$, a
contradiction. ∎

As a result, we can equivalently aggregate vertices $v$ in each $Y_{i}$ under
a (seemingly) weaker requirement that $v$ lies strictly on the left side of
$\Phi_{b_{i-1},b_{i}}$, $\Phi_{b_{i},b_{i+1}}$, $\Phi_{b_{i+1},b_{i+2}}$, and
$\Phi_{b_{i+2},b_{i+3}}$. But this is, again, part of the precomputed data for
the tuple $(b_{i-1},b_{i},b_{i+1},b_{i+2},b_{i+3})$.

Consequently, there are $k$ disjoint sets $Y_{i}$ to consider. We can thus
aggregate weights or construct a list for reporting vertices from
$v\in\Pi_{P}(B)\setminus\partial{P}$ strictly inside $\Phi$ in $O(k)$ time. We
thus obtain:

######  Lemma 5.6.

The base case can be handled in $O(|B|)$ time.

##### General case.

To solve the general case, we reduce it to a number of base case instances. To
this end, we maintain a partition of $B=S\cup T$ such that $S$ precedes $T$ on
$\Phi$. Let $S=\\{s_{1},\ldots,s_{p}\\}$ and $T=\\{t_{1},\ldots,t_{q}\\}$. We
will gradually simplify the problem while maintaining the following
invariants:

  1. (1)

For any $u,v\in B$, if $u$ can reach $v$ in $P$, then $\pi_{u,v}\subseteq
P[\Phi]$.

  2. (2)

For any $1\leq i<j\leq p$, if $s_{i}$ can reach $s_{j}$ or can be reached from
$s_{j}$, then $j=i+1$.

  3. (3)

If $x,y\in B$ are neighbors in the counterclockwise order $\prec_{h}$ on
$\Phi$ and $\Phi_{x,y}=\pi_{\\{x,y\\}}$, then $x,y\in S$.

  4. (4)

In the data structures $\mathcal{L},\mathcal{L}^{R}$ of Lemma 5.3, the set $Z$
satisfies $Z=S\setminus\\{s_{p}\\}$.

The algorithm will gradually modify $B,S,T,\Phi$ until we have $S=B$ and
$T=\emptyset$. Note that when $T=\emptyset$, $(B,\Phi)=(S,\Phi)$ satisfies the
requirement of the base case and can be solved in $\widetilde{O}(|B|)$ time.

Initially we put $\Phi=h$, $S=\\{b_{1},b_{2}\\}$, and insert $b_{1}$ to $Z$ to
satisfy the invariants.

The main loop of the procedure runs while $T\neq\emptyset$ and does the
following. Using $\mathcal{L}$ and $\mathcal{L}^{R}$, in
$O(\operatorname{polylog}{n})$ time we test whether $t_{1}$ can reach $Z$ or
can be reached from $Z$ in $P$. If this is not the case, we simply move
$t_{1}$ to the end of $S$, an update $Z$ accordingly. Note that $|T|$
decreases then.

Otherwise, we can find all vertices $X=\\{x_{1},\ldots,x_{l}\\}\subseteq Z$
that $t_{1}$ can reach or can be reached from in $\widetilde{O}(|X|)$ by
repeatedly extracting them from the data structures
$\mathcal{L},\mathcal{L}^{R}$. Additionally we sort $X$ so that the order
$x_{1},\ldots,x_{l}$ matches the order of $S$ on $\Phi$. Let $\pi_{i}$ denote
the path $\pi_{\\{t_{1},x_{i}\\}}$ possibly reversed to go from $t_{1}$ to
$x_{i}$, and $\pi_{i}^{R}$ denote the reverse $\pi_{i}$ going from $x_{i}$ to
$t_{1}$. The vertices $X$ are used to ’’cut off‘‘ $l$ base case instances, as
follows. For $i=0,\ldots,l$, let $S_{i}$ denote the vertices of $S$ between
$x_{i}$ and $x_{i+1}$ on $\Phi$ (inclusive), where we set $x_{l+1}:=s_{p}$,
$x_{0}:=s_{1}$. We split the problem $(B,\Phi)$ into the following subproblems
(see Figure 1 for better understanding):

  1. 1.

For each $i=1,\ldots,l-1$, an instance
$(S_{i}\cup\\{t_{1}\\},\Phi_{x_{i},x_{i+1}}\cdot\pi_{i+1}^{R}\cdot\pi_{i})$.

  2. 2.

An instance $(S_{l}\cup\\{t_{1}\\},\Phi_{x_{l},t_{1}}\cdot\pi_{l})$.

  3. 3.

An instance $(S_{0}\cup
T,\Phi_{s_{1},x_{1}}\cdot\pi_{1}^{R}\cdot\Phi_{t_{1},s_{1}})$.

$s_{1}$$s_{2}$$x_{1}={\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}s_{g}}$$x_{2}$$x_{3}$$x_{4}$$s_{p}$$t_{1}$$t_{2}$$t_{q}$$\pi_{1}=\pi_{t_{1},x_{1}}$$\pi_{2}=\pi_{t_{1},x_{2}}$$\pi_{3}=\pi_{t_{1},x_{3}}$$\pi_{4}$
Figure 1: Splitting the instance $(B,\Phi)$, where $B=S\cup T$, into 5 smaller
instances with paths $\pi_{1},\ldots,\pi_{l}$ (either originating or ending in
$t_{1}$) for $l=4$. The vertices $S=\\{s_{1},\ldots,s_{p}\\}$ are shown in
blue, whereas the vertices $T=\\{t_{1},\ldots,t_{q}\\}$ in red. The black
arrows and dashed lines represent the individual parts of the curve $\Phi$:
paths of the form $\pi_{u,v}$ or parts of the curve $h$, respectively. Note
that the black arrows appear only on the $\Phi_{s_{1},s_{p}}$ part of $\Phi$.
The vertices $x_{1},\ldots,x_{4}$, marked green, are precisely all the
vertices of $S\setminus\\{s_{p}\\}$ that $t_{1}$ can reach or can be reached
from. The obtained smaller instances are marked with distinct patterns. The
instances marked with line patterns (types 1 or 2) are base instances. The
instance marked using a dotted pattern (type 3) might constitute the only
obtained instance that is not a base instance (for which the algorithm
continues).

######  Lemma 5.7.

For each of the above subproblems $(B^{\prime},\Phi^{\prime})$, and $u,v\in
B^{\prime}$, if $u$ can reach $v$ in $P$, then $\pi_{u,v}\subseteq
P[\Phi^{\prime}]$.

###### Proof.

Note that $(B^{\prime},\Phi^{\prime})$ is obtained from $(B,\Phi)$ by cutting
it out of $(B,\Phi)$ with at most two paths
$\pi_{\\{t_{1},a\\}},\pi_{\\{t_{1},b\\}}$, for some $t_{1},a,b\in
B^{\prime}\subseteq B$. By our assumption, $\pi_{u,v}\subseteq P[\Phi]$. As a
result, if $\pi_{u,v}$ was not contained in $P[\Phi^{\prime}]$, then
$\pi_{u,v}$ would need to cross either $\pi_{\\{t_{1},a\\}}$ or
$\pi_{\\{t_{1},b\\}}$. However, this is impossible by Lemma 5.2 and since
$u,v\in V(P[\Phi^{\prime}])$. ∎

######  Lemma 5.8.

The obtained instances of types 1 and 2 above fall into the base case.

###### Proof.

To see that the base case requirement is satisfied, recall that by the
invariant posed on $S$, if two elements of $S_{i}$, where
$i\in\\{1,\ldots,l\\}$, are related (wrt. reachability in $P$), they are
neighboring in $S_{i}$. By construction, $t_{1}$ can be only related to the
first and the last element of $S_{i}$. ∎

Since the cutting is performed using non-crossing paths in $P$, the regions
$P[\Phi^{\prime}]$ for the obtained subproblems can only share their
boundaries, that is, if some $v$ is strictly inside one of the curves
$\Phi^{\prime}$, then it it is not strictly inside another obtained curve
$\Phi^{\prime\prime}$. Therefore, if we proceeded with the above subproblems
recursively, we would not aggregate or report any vertex of
$v\in\Pi_{P}(B)\setminus\partial{P}$ twice. However, we still need to
report/aggregate vertices that lie on paths $\pi_{1},\ldots,\pi_{l}$ strictly
inside the curve $\Phi$. We now discuss how this strategy is implemented. Let
us first consider solving the subproblems recursively. We handle all the
obtained base case instance of types 1 and 2 as explained before. If
$x_{1}=s_{g}$, then by Lemma 5.6, the total time required for this is
$O\left(\sum_{i=1}^{l}(|S_{i}|+1)\right)=O((p-g)+l)$. But note that $l\leq
p-g$, so in fact the bound is $O(p-g)$.

To handle the instance $(S_{0}\cup
T,\Phi_{s_{1},x_{1}}\cdot\pi_{1}^{R}\cdot\Phi_{t_{1},s_{1}})$, we simply
replace $(B,\Phi)$ with it and proceed with solving it using the algorithm for
the general case. To this end, we set $S:=S_{0}\cup\\{t_{1}\\}$,
$T:=\\{t_{2},\ldots,t_{q}\\}$ and update $Z$ in the data structures
$\mathcal{L},\mathcal{L}^{R}$ to $S_{0}$ by removing elements. Then, invariant
(1) is satisfied by Lemma 5.7, and invariants (2), (3) and (4) are satisfied
by construction. This way, in $\widetilde{O}(\Delta)$ time we reduce the
instance $(B,\Phi)$ by $\Delta=|S|-|S_{0}|=p-g$ vertices. Recall that
$Z=S\setminus\\{s_{p}\\}$ implies that $g<p$. Thus, $\Delta\geq 1$ and the
sizes of $B$ and $T$ strictly decrease.

Let us now discuss how to aggregate/report the vertices of
$\Pi_{P}(B)\setminus\partial{P}$ that lie on any of the paths
$\pi_{1},\ldots,\pi_{l}$ (that are not handled in any of the subproblems), but
at the same time lie strictly inside $\Phi$ (before altering $(B,\Phi)$).
Since $\Phi$ is formed of either the edges of the hole $h$, or from the paths
$\pi_{\\{u,v\\}}$, and each $\pi_{i}$ is contained in $P[\Phi]$, equivalently
we need to aggregate the vertices of $\Pi_{P}(B)\setminus\partial{P}$ on the
paths $\pi_{1},\ldots,\pi_{l}$ that do not lie on $\Phi$.

Observe that since $x_{1},\ldots,x_{l}$ lie on $\Phi$ in that order, and the
paths $\pi_{1},\ldots,\pi_{l}$ all lie in $P[\Phi]$ and are non-crossing by
Lemma 5.2, for any three $i<j<k$, we have $V(\pi_{i})\cap V(\pi_{k})\subseteq
V(\pi_{j})$. As a result, any vertex on these paths is included in precisely
one of the sets $V(\pi_{i})\setminus V(\pi_{i-1})$, for $i=1,\ldots,l$ and
$V(\pi_{0}):=\emptyset$. Moreover, in Lemma 5.9 we will show that each
$\pi_{i}$ can possibly have a non-empty intersection with $O(1)$ parts
(between neighboring elements of $B$) of $\Phi$, that we can also identify in
$O(1)$ time. Since, by Lemma 5.2, for every path $\pi_{\\{u,v\\}}$, the
intersection of $\pi_{\\{u,v\\}}$ with $\pi_{i}$ is either empty or forms a
subpath of $\pi_{i}$, aggregating or reporting the required vertices of
$\pi_{i}$ boils down to aggregating or reporting the vertices of
$V(P)\setminus\partial{P}$ on some $O(1)$ subpaths of $\pi_{i}$ that form what
remains from $\pi_{i}$ after removing $O(1)$ of its intersections with other
paths $\pi_{u,v}$.

######  Lemma 5.9.

Consider the moment when the split into subproblems happens. Suppose
$x_{i}=s_{j}$. Let $u,v\in B$ be neighboring on $\Phi$, so that $u$ comes
before $v$ in the counterclockwise order $\prec_{h}$ on $\Phi$. Then
$(V(\pi_{i})\cap V(\Phi_{u,v}))\setminus\partial{P}\neq\emptyset$ implies that
$u=s_{j^{\prime}}$ for some $j^{\prime}\in\\{1,\ldots,p\\}$ such that
$|j-j^{\prime}|\leq 2$.

###### Proof.

Recall that the curve is $\pi_{i}$ is either the path
$\pi_{\\{x_{i},t_{1}\\}}$ or its reverse. Let us only consider the case when
$\pi_{\\{x_{i},t_{1}\\}}=\pi_{x_{i},t_{1}}$; the case when
$\pi_{\\{x_{i},t_{1}\\}}=\pi_{t_{1},x_{i}}$ is analogous.

By invariant (3), we have that $u,v\in S$ since otherwise $\Phi_{u,v}$ is a
part of the curve $h$ and therefore does not contain any vertices from outside
$V(h)$. So $\\{u,v\\}=\\{s_{j^{\prime}},s_{j^{\prime}+1}\\}$ for some
$j^{\prime}\in\\{1,\ldots,p-1\\}$. Let $z\in(V(\pi_{i})\cap
V(\Phi_{u,v}))\setminus\partial{P}$. If
$\Phi_{u,v}=\pi_{s_{j^{\prime}},s_{j^{\prime}+1}}$, then the $z\to v$ subpath
of $\Phi_{u,v}$ and the $x_{i}\to z$ subpath of $\pi_{i}$ together form an
$s_{j}\to s_{j^{\prime}+1}$ path in $P$, which by invariant (2) implies
$j^{\prime}+1\in\\{j-1,j,j+1\\}$, and thus $j^{\prime}\in[j-2,j]$. If
$\Phi_{u,v}=\pi_{s_{j^{\prime}+1},s_{j^{\prime}}}$, then, analogously, there
exists an $s_{j}\to s_{j^{\prime}}$ path in $P$, so $j^{\prime}\in[j-1,j+1]$.
∎

By Lemma 5.9, for each $\pi_{i}$, we need to report all vertices of $\pi_{i}$
from outside $\partial{P}$, except those on the union of at most $6$ subpaths
of $\pi_{i}$. Since the subpaths are always intersections of some two paths
$\pi_{u,v}$, we can identify these subpaths using precomputed data in $O(1)$
time. Aggregating vertex weights not on at most $6$ subpaths of $\pi_{i}$ is
the same as aggregating weights on at most $7$ disjoint subpaths of $\pi_{i}$.
Recall that we have precomputed the aggregate weights for all the subpaths of
all the possible $\pi_{u,v}$. As a result, aggregating or reporting vertices
$\Pi_{P}(B)\setminus\partial{P}$ that lie on any of the paths
$\pi_{1},\ldots,\pi_{l}$ takes $O(l)=O(p-g)$ time.

######  Lemma 5.10.

The general case can be handled in $\widetilde{O}(|B|)$ time.

###### Proof.

Recall that when $T=\emptyset$, we have a base instance that can be solved in
$O(|B|)$ time.

Every iteration of the main loop that does not involve changing $B$ takes
$O(\operatorname{polylog}{n})$ time and reduces the size of $T$ by one. But
the set $T$ can shrink at most $|B|$ times, so such iterations cost
$\widetilde{O}(|B|)$ time in total. Every other iteration of the main loop
involves reducing the size of $B$ by some $\Delta>0$ in
$\widetilde{O}(\Delta)$ time. Such iterations clearly cost
$\widetilde{O}(|B|)$ time in total as well. ∎

###  5.7 Handling multiple-hole queries

In this section we discuss how to drop the simplifying assumption that the
query set $A\subseteq\partial{P}$ lies entirely on a single hole of $P$.

Before we continue, let us remark that in Section 5 we did not fully leverage
the fact that the holes‘ bounding cycles of a piece of an $r$-division with
few holes contain vertices from $\partial{P}$ exclusively. Indeed, we only
used that (i) $A$ lies on a single face $h$ of $P$, and (ii) that there was no
need to report or aggregate vertices lying on the bounding cycle of $h$ –
indeed, in a piece of an $r$-division with few holes no vertex of
$V(P)\setminus\partial{P}$ lies on the bounding cycle of $h$.

In the following, we will slightly relax the problem: define $\partial^{*}{P}$
to contain all the vertices of $P$ on the bounding cycles of
$h_{1},\ldots,h_{k}$, and let $\partial{P}$ be an arbitrary fixed subset of
$\partial^{*}{P}$ of size $O(\sqrt{r})$ (but the set $\partial^{*}{P}$ can be
possibly larger). Given $A\subseteq\partial{P}$, the query‘s objective is to
aggregate/report vertices of $\Pi_{P}(A)\setminus\partial^{*}{P}$. By the
above discussion, the data structure of Section 5 can actually solve this
slightly more general problem within the same bounds. Moreover, as discussed
in Section 5.2, we no longer use the assumption of Theorem 4.3 that
$\Pi_{P}(A)\cap\partial{P}=A$ which was only required to reduce to the acyclic
case.

Denote by $\partial_{i}^{*}{P}$, for $i=1,\ldots,k$, the vertices of
$\partial^{*}{P}$ that lie on the hole $h_{i}$. Recall that $k=O(1)$. The sets
$\partial_{1}^{*}{P},\ldots,\partial_{k}^{*}{P}$ are not necessarily disjoint.
We now describe how to reduce the problem, roughly speaking, to the case when
$P$ has one hole less. The reduction will require $O(r^{3})$ additional
preprocessing and will add only $O(|A|)$ overhead to the query procedure. The
reduction will preserve acyclicity.

####  5.7.1 Preprocessing

Suppose first that there exist no such $s\in\partial_{i}^{*}{P}$ and
$t\in\partial_{j}^{*}{P}$, where $i\neq j$, that $s$ can reach $t$ in $P$.
This can be clearly checked in $O(|P|)=O(r)$ time by running graph search $k$
times. In this case, we have that $\Pi_{P}(A)\setminus\partial^{*}{P}$ is a
disjoint sum of
$\Pi_{P}(A\cap\partial^{*}_{i}{P})\setminus\partial^{*}_{i}{P}$. Hence, all we
do is simply apply the preprocessing of Section 5 $k$ times, for each hole
$h_{i}$ independently, i.e., we set $\partial^{*}{P}:=\partial^{*}_{i}{P}$ and
$\partial{P}:=\partial{P}\cap\partial^{*}_{i}{P}$ in the $i$-th single-hole
data structure. This takes $\widetilde{O}(kr^{3})=\widetilde{O}(r^{3})$ time.

Let us now assume that such $s,t$ exist and pick them so that we can find a
_simple_ $s\to t$ path $Q$ such that $V(Q)\cap\partial^{*}{P}=\\{s,t\\}$ (we
might possibly have $s=t$). For example, such a path $Q$ can be found in
$O(r)$ time by computing, for each pair of holes of $P$, a shortest path
between these two holes, and taking the shortest out of these paths as $Q$.
Wlog. let us renumber the sets $\partial^{*}_{i}{P}$ so that
$s\in\partial^{*}_{1}{P}$ and $t\in\partial^{*}_{2}{P}$.

For every $b\in\partial{P}$, we compute (i) the first vertex
$\textrm{first}_{b}$ on the path $Q$ that $b$ can reach in $P$, and (ii) the
last vertex $\textrm{last}_{b}$ on $Q$ that can reach $b$ in $P$. All the
vertices $\textrm{first}_{b}$ and $\textrm{last}_{b}$ (that exist) can be
computed in $O(r)$ time via graph search (see e.g. [Tho04]).

Let us obtain a graph $P^{\prime}$ from $P$ by cutting along the path
$Q=u_{1}\ldots u_{q}=s\to t$. Formally, the path $Q$ is replaced with two
copies $Q^{\prime}=u_{1}^{\prime}\ldots u_{q}^{\prime}$ and
$Q^{\prime\prime}=u_{1}^{\prime\prime}\ldots u_{q}^{\prime\prime}$, but the
copies $u_{i}^{\prime},u_{i}^{\prime\prime}$ of the vertex $u_{i}$ are not
connected. Neither the vertices nor the edges of $Q$ are contained in the
graph $P^{\prime}$, only $Q^{\prime}$ and $Q^{\prime\prime}$ are there. For
all $v\in V(P)\setminus V(Q)$, for convenience we set
$v^{\prime}=v^{\prime\prime}:=v$. Clearly, $P^{\prime}$ is acyclic if $P$ is
acyclic.

We set the boundary of $P^{\prime}$ to be:

$\partial{P^{\prime}}:=\partial{P}\setminus\\{s,t\\}\cup\bigcup_{b\in\partial{P}}\\{\textrm{first}_{b}^{\prime},\textrm{first}_{b}^{\prime\prime},\textrm{last}_{b}^{\prime},\textrm{last}_{b}^{\prime\prime}\\}.$

Note that the two holes $h_{1},h_{2}$ of $P$ are merged into a single hole $h$
in $P^{\prime}$. As a result, and since all the vertices
$\partial{P^{\prime}}\setminus\partial{P}$ lie on $h$, $P^{\prime}$ has less
holes (that is, faces containing boundary vertices $\partial{P^{\prime}}$)
than $P$. Moreover, we have (recall that $\partial^{*}{P^{\prime}}$ denotes
all vertices on the holes of $P^{\prime}$):

$\partial^{*}{P^{\prime}}:=\partial^{*}{P}\setminus\\{s,t\\}\cup
V(Q^{\prime})\cup V(Q^{\prime\prime}).$

Observe that $|P^{\prime}|\leq 3|P|=O(r)$ and $|\partial{P^{\prime}}|\leq
5|\partial{P}|$ so $|\partial{P^{\prime}}|=O(\sqrt{r})$. We recursively build
a data structure supporting desired queries
$A^{\prime}\subseteq\partial{P^{\prime}}$ on the graph $P^{\prime}$ as defined
above.

Finally, for all the subpaths $R$ of $Q$ we precompute the aggregate weights
of all the vertices of $V(R)\setminus\partial^{*}{P}=V(R)\setminus\\{s,t\\}$.
This can be done in $O(r^{3})$ time using a brute force algorithm.

Since the piece $P$ has initially size $O(r)$, $|\partial{P}|=O(\sqrt{r})$ and
$\partial{P}$ lies on $k=O(1)$ holes of $P$, after at most $k-1$ recursive
preprocessing steps we will arrive at the single-hole case (when a pair $s,t$
cannot be found, possibly because $k=1$). In each of the recursive data
structures, the input piece has size $2^{O(k)}\cdot O(r)=O(r)$, and has
$|\partial{P}|=2^{O(k)}\cdot O(\sqrt{r})=O(\sqrt{r})$. At each of the $O(1)$
recursive levels, the additional preprocessing takes $O(r^{3})$ time.

####  5.7.2 Query

Given $A\subseteq\partial{P}$, the query procedure is as follows. If $P$ is at
the lowest level of the recursive data structure, then we split $A$ into
$O(1)$ sets $A_{i}=A\cap\partial_{i}^{*}{P}$. For each of the sets $A_{i}$ we
run the single-hole query procedure independently. Since there are no paths
between boundary vertices on distinct holes, we can aggregate the results in
an obvious way. This is justified by the fact that
$\Pi_{P}(A)\setminus\partial^{*}{P}$ is a disjoint union of the $O(1)$ sets
$\Pi_{P}(A\cap\partial_{i}^{*}{P})\setminus\partial^{*}{P}$. Clearly, the
query algorithm runs in $\widetilde{O}(|A|)$ time in this case.

Otherwise, if $P$ is not leaf-level in the recursion, let $\prec$ denote the
natural order on vertices of the path $Q$. Let
$f=\min_{\prec}\\{\textrm{first}_{a}:a\in A\\}$ and
$l=\max_{\prec}\\{\textrm{last}_{a}:a\in A\\}$. We construct the set

$A^{\prime}:=\begin{cases}(A\cap\partial{P^{\prime}})\cup\\{f^{\prime},f^{\prime\prime},l^{\prime},l^{\prime\prime}\\}&\text{
if }f\preceq l,\\\ A\cap\partial{P^{\prime}}&\text{ otherwise. }\end{cases}$

Clearly, $A^{\prime}\subseteq\partial{P^{\prime}}$ can be constructed in
$O(|A|)$ time and has size $O(|A|)$. Note that $A^{\prime}$ might not satisfy
$\Pi_{P^{\prime}}(A^{\prime})\cap\partial{P^{\prime}}=A^{\prime}$, but we do
not need that assumption if $P^{\prime}$ is acyclic, as discussed before. We
issue a query about $A^{\prime}$ to the data structure built recursively on
$P^{\prime}$ which has one hole less. That data structure produces aggregate
weight $\sigma$ of
$\Pi_{P^{\prime}}(A^{\prime})\setminus\partial^{*}{P^{\prime}}$ or an iterator
reporting the elements of that set in $O(1)$ time. To lift $\sigma$ to the
desired aggregate weight for $\Pi_{P}(A)\setminus\partial^{*}{P}$, we simply
additionally add the precomputed aggregate weight of the subpath $Q[f,l]$
(except $s,t\in\partial^{*}{P}$). To lift the reporting function, we simply
report the vertices $V(Q[f,l])\setminus\\{s,t\\}$ after we have finished
reporting $\Pi_{P^{\prime}}(A^{\prime})\setminus\partial^{*}{P^{\prime}}$.
Recall that $V(Q[f,l])\setminus\\{s,t\\}$ is disjoint with
$\Pi_{P^{\prime}}(A^{\prime})\setminus\partial^{*}{P^{\prime}}$ by
construction.

We now prove the correctness of this algorithm.

######  Lemma 5.11.

For any $A\subseteq\partial{P}$, we have
$\Pi_{P}(A)\setminus\partial^{*}{P}=(\Pi_{P^{\prime}}(A^{\prime})\setminus\partial^{*}{P^{\prime}})\cup(V(Q[f,l])\setminus\\{s,t\\})$.

###### Proof.

Let us start with the ’’$\supseteq$‘‘ direction. Suppose first that
$v\in\Pi_{P^{\prime}}(A^{\prime})\setminus\partial^{*}{P^{\prime}}$. Since we
have $V(P^{\prime})\setminus V(P)\subseteq\partial^{*}{P^{\prime}}$ and
$s,t\notin V(P^{\prime})$, we have $v\in V(P)\setminus\partial^{*}{P}$.
Moreover, $v$ lies on some path $R^{\prime}=a\to b$ between vertices of
$A^{\prime}$ in $P^{\prime}$. Since every vertex (edge) of $P^{\prime}$ is a
either an original vertex (edge, resp.) or a copy of a vertex (edge, resp.) of
$P$, there is a path $R=a_{0}\to b_{0}$ in $P$ whose $R^{\prime}$ is a copy
of. If $a_{0},b_{0}\in A$, then we have
$v\in\Pi_{P}(A)\setminus\partial^{*}{P}$ immediately. Otherwise, if e.g.,
$a_{0}\notin A$, then $f\preceq l$ and $a_{0}\in\\{f,l\\}$. However, by the
definition of $f$, $f$ is reachable from a vertex $c\in A$. Since a path $f\to
l$ exists in $P$ as a subpath of $Q$, $l$ is reachable from $c$ as well. As a
result, even if $a_{0}\notin A$, $a_{0}$, and thus also $v$, is reachable from
$A$ in $P$. Analogously one can argue that $b_{0}$, and thus also $v$, can
reach $A$ in $P$.

Now consider $v\in V(Q[f,l])\setminus\\{s,t\\}$. Then, $f\preceq l$ and we
similarly argue that $v$ can be reached from $f$ and can reach $l$ and as a
result can reach and can be reached from $A$ in $P$.

Let us now move to the more challenging ’’$\subseteq$‘‘ direction. Consider
some $v\in\Pi_{P}(A)\setminus\partial^{*}{P}$. There exists a path $R=a\to
v\to b$ in $P$ with $a,b\in A$. If $V(R)\cap V(Q)=\emptyset$, then the path
$R$ is preserved in the graph $P^{\prime}$. Moreover,
$a,b\in\partial{P}\setminus\\{s,t\\}$ and thus $a,b\in A^{\prime}$. We obtain
$v\in\Pi_{P^{\prime}}(A^{\prime})\setminus\partial^{*}{P^{\prime}}$ by
$v\notin V(Q)$, as desired. Hence, in the following we assume $V(R)\cap
V(Q)\neq\emptyset$. Note that this also implies that $f\preceq l$ since $A$
can reach $Q$ and be reached from $Q$.

First suppose that $v\in V(Q)\cap V(R)$. Since $v\notin\partial^{*}{P}$,
$v\notin\\{s,t\\}$. By the definition of $f,l$, we have $f\preceq v\preceq l$
and thus $v\in V(Q[f,l])\setminus\\{s,t\\}$, as desired.

Now assume $v\in V(R)\setminus V(Q)$. Note that $v\notin\partial^{*}{P}\cup
V(Q)$ implies $v=v^{\prime}=v^{\prime\prime}\notin\partial^{*}{P^{\prime}}$.
Let $x,y$ denote the first and the last vertex of $Q$ on $R$, respectively.
Let $R=R_{1}\cdot R_{2}\cdot R_{3}$, where $R_{1}=a\to x$ and $R_{3}=y\to b$.
Observe that the paths $R_{1}$ and $R_{3}$ are preserved in $P^{\prime}$,
except $R_{1}$ reaches a copy of $x$, and $R_{3}$ starts at a copy of $y$.
Moreover, note that $x\preceq y$ by acyclicity, and thus we have
$f\preceq\textrm{first}_{a}\preceq x\preceq y\preceq\textrm{last}_{b}\preceq
l$.

Consider the case $v\in V(R_{1})\setminus V(Q)$. Assume wlog. that $R_{1}$
joins the path $Q$ in $P$ in such a way that $R_{1}$ is preserved as
$R_{1}^{\prime}=a^{\prime}\to x^{\prime}$ in $P^{\prime}$. Now, observe that
the path $R_{1}^{\prime}\cdot Q^{\prime}[x^{\prime},l^{\prime}]$ is an
$a^{\prime}\to l^{\prime}$ path in $P^{\prime}$ containing the vertex $v$, and
$l^{\prime}\in A^{\prime}$. If $a\notin\\{s,t\\}$, then clearly also
$a^{\prime}\in A^{\prime}$. Otherwise, if $a=s$, then $f=s$ and thus
$a^{\prime}=f^{\prime}$, whereas if $a=t$, then $l=t$ and thus
$a^{\prime}=l^{\prime}$. In all cases $\\{a^{\prime},l^{\prime}\\}\subseteq
A^{\prime}$. As a result, indeed
$v\in\Pi_{P^{\prime}}(A^{\prime})\setminus\partial^{*}{P^{\prime}}$. One can
proceed with the case $v\in V(R_{3})\setminus V(Q)$ symmetrically.

Finally, suppose $v\in V(R_{2})$. Then, split $R_{2}$ into maximal subpaths
with only their endpoints lying on the path $Q$. One of the obtained maximal
subpaths $S=c\to d$, where $c,d\in V(Q)$, goes through $v$. Again, we have
$f\preceq\textrm{first}_{a}\preceq c\preceq d\preceq\textrm{last}_{b}\preceq
l$. Moreover, $S$ is preserved in $P^{\prime}$ as wlog. the path
$S^{\prime\prime}=c^{\prime\prime}\to d^{\prime\prime}$. But then
$Q^{\prime\prime}[f^{\prime\prime},c^{\prime\prime}]\cdot
S^{\prime\prime}\cdot Q^{\prime\prime}[d^{\prime\prime},l^{\prime\prime}]$ is
a $f^{\prime\prime}\to l^{\prime\prime}$ path in $P^{\prime}$ that goes
through $v$. Since $f^{\prime\prime},l^{\prime\prime}\in A^{\prime}$, we again
obtain $v\in\Pi_{P^{\prime}}(A^{\prime})\setminus\partial^{*}{P^{\prime}}$, as
desired. ∎

When queried about the set $A$, the recursive data structures are passed a set
$A^{\prime}$ with $|A^{\prime}|=|A|+O(1)=O(|A|)$. As a result, the query time
is dominated by the $\widetilde{O}(|A^{\prime}|)=\widetilde{O}(|A|)$ time used
by the bottommost single-hole data structure. This finishes the proof of
Theorem 4.3.

###  5.8 The existential reachability data structure

In this section, we prove the following. See 5.3

We will use the following property of reachability between vertices lying on a
single face of a planar digraph $P$ essentially proved in [IKŁS17].

######  Lemma 5.12.

[IKŁS17] Let the vertices $Y$ lie on a single face $h$ of a planar digraph
$P$. Then in $\widetilde{O}(|P|+|Y|^{2})$ time one can compute $O(|Y|)$ pairs
of subsets $S_{i},T_{i}\subseteq Y$ such that:

  1. 1.

For any $i$, the elements $T_{i}$ have an associated linear order $\prec_{i}$.

  2. 2.

For any $i$ and $s\in S_{i}$, there exist such vertices $l_{i,s},r_{i,s}$ that
for any $t\in T_{i}$, $s$ can reach $t$ in $P$ iff
$l_{i,s}\preceq_{i}t\preceq_{i}r_{i,s}$.

  3. 3.

Every $v\in Y$ is contained in $O(\log{|Y|})$ subsets $S_{i}$ and
$O(\log{|Y|})$ subsets $T_{i}$.

  4. 4.

For any $u,v\in Y$, if $u$ can reach $v$ in $P$, then there exists such $i$
that $(u,v)\in S_{i}\times T_{i}$.

###### Proof sketch..

Split $Y$ into two disjoint parts $A,B$ such that $A\cup B=Y$,
$|A|,|B|\leq\left\lceil|Y|/2\right\rceil$, and both $A,B$ appear consecutively
on $h$. Let $T$ denote the vertices of $B$ that can be reached from some
vertex of $A$ in $P$. Similarly, let $S$ denote the vertices of $A$ that can
reach $B$ in $P$. Let $\prec$ be the counterclockwise order on $T$ starting
with the vertex that appears earliest after a vertex of $A$ in the
counterclockwise order of $Y$ on $h$. One can easily prove (see [IKŁS17]) that
each $s\in S$ can in fact reach some number of vertices that appear
consecutively in $T$. As a result, there exist such $l_{s},r_{s}\in T$ that
for any $t\in T$, $s$ can reach $t$ in $P$ iff $l_{s}\preceq t\preceq r_{s}$.

We include the pair $(S,T)$ along with the order $\prec$, and the vertices
$\\{l_{s},r_{s}:s\in S\\}$ in the constructed family. The obtained pair
encodes the reachability from the vertices $A$ to vertices $B$ in $P$: if
$a\in A$ can reach $b\in B$ in $T$ then clearly $a\in S$, $b\in T$. Note that
the subsets $S,T$ can be constructed in $\widetilde{O}(|Y|^{2})$ time if only
we can answer reachability queries in $P$ in $O(\operatorname{polylog}{n})$
time. This is indeed possible after $\widetilde{O}(|P|)$ time preprocessing
[Tho04].

Symmetrically we can deal with the reachability from the vertices $B$ to the
vertices $A$ in $P$. It remains to handle reachability between pairs of
vertices inside the set $A$, and between pairs inside $B$. This is done
recursively. Since $|A|,|B|\leq\lceil|Y|/2\rceil$, each vertex of the original
input set $Y$ will appear in $O(\log|Y|)$ recursive calls, and thus in
$O(\log|Y|)$ sets $S_{i}$ or $T_{i}$. It is easy to check that the algorithm
produces all the pairs $(S_{i},T_{i})$ in $\widetilde{O}(|Y|^{2})$ time. ∎

###### Proof of Lemma 5.3.

We first compute the sets $(S_{i},T_{i})$ from Lemma 5.12 applied to
$Y:=\partial{P}\cap V(h)$ (along with the orderings $\prec_{i}$, and all the
vertices $l_{i,v},r_{i,v}$) in
$\widetilde{O}(|P|+|\partial{P}|^{2})=\widetilde{O}(r)$ time. The data
structure simply stores the sets $T_{i}\cap Z$ for all $i$ sorted according to
$\prec_{i}$, each of them in a balanced binary search tree. Note that when an
element $b$ is inserted or removed from $Z$, it is enough to update
$O(\log{r})$ sets $T_{i}\cap Z$ as $b$ is contained in $O(\log{r})$ sets
$T_{i}$.

To answer a query, that is, find a vertex $z\in Z$ reachable from a query
vertex $v$, for each of the $O(\log{r})$ indices $i$ such that $v\in S_{i}$ we
check whether the set $T_{i}\cap Z$ contains an element $z$ between $l_{i,s}$
and $r_{i,s}$ inclusive, wrt. $\prec_{i}$. This clearly takes $O(\log{r})$
time. By Lemma 5.12, $s$ can reach a vertex in $Z$ if and only if at least one
$z$ is found this way.

We conclude that both the update and the query time of the data structure is
$O(\log^{2}{r})$. ∎

##  6 Fully dynamic #SSR in planar digraphs

In this section, we sketch how a data structure summarized by the below lemma
can be obtained.

######  Lemma 6.1.

Let $G$ be a planar digraph subject to planarity-preserving edge insertions
and deletions. There exists a data structure with $\widetilde{O}(n^{4/5})$
worst-case update time supporting counting the vertices reachable from a query
vertex $s$ in $\widetilde{O}(n^{4/5})$ time.

We again use the same template as in Sections 3 and 4: as a base, we maintain
an $r$-division $\mathcal{R}$ with few holes, along with the piecewise
reachability certificates $X_{P}$.

In addition, we leverage the additively-weighted Voronoi diagram data
structure of [GKM+21]. Before stating the interface and characteristics of
that data structure, we need to introduce some more notation. Suppose $H$ is a
non-negatively weighted plane digraph. Let ${\partial{H}\subseteq V(H)}$ be
the set of vertices of $H$ lying on some $O(1)$ fixed faces of $H$ (and
containing all vertices of these faces) and such that every $v\in V(H)$ is
reachable from $\partial{H}$ in $H$. Let $\omega:\partial{H}\to\mathbb{R}$ be
a _weight function_ such that for any $v\in V(H)$,
$\omega(s)+\text{dist}_{H}(s,v)$ has a unique minimizer $s\in\partial{H}$. The
_additively weighted Voronoi diagram_ wrt. $\omega$ is the partition of $V(H)$
into disjoint subsets (cells) $\text{Vor}(s)$, $s\in\partial{H}$, such that
$\text{Vor}(s)$ contains precisely the vertices $v$ such that $s$ minimizes
$\omega(s)+\text{dist}_{H}(s,v)$. Note that by our assumptions on $H$, if
$v\in\text{Vor}(s)$, then $\omega(s)+\text{dist}_{H}(s,v)\neq\infty$. The
complexity $|\partial{\text{Vor}(s)}|$ of $\text{Vor}(s)$ is defined to be the
number of faces of $H$ whose vertices include elements of $\text{Vor}(s)$ and
at least two other cells. One can prove that
$\sum_{s\in\partial{H}}|\partial{\text{Vor}(s)}|=O(|\partial{H}|)$ [GKM+21].

######  Theorem 6.2.

[GKM+21] Let $H$ be as defined above. In
$\widetilde{O}\left(|H|\cdot|\partial{H}|^{2}\right)$ one can construct a data
structure such that for any $\omega$ satisfying the assumptions outlined
above, it can build a representation of the additively-weighted Voronoi
diagram wrt. $\omega$ in $\widetilde{O}(|\partial{H}|)$ time. The
representation allows, among others, computing all the cell sizes
$|\text{Vor}(s)|$, $s\in\partial{H}$, in $\widetilde{O}(|\partial{H}|)$ total
time.

###### Proof sketch..

This is essentially a special case of [GKM+21, Theorem 1.1]. There, it is
stated that after the representation is built, one can compute, for any
$s\in\partial{H}$, the furthest vertex $v\in\text{Vor}(s)$ (i.e., $v$
maximizing $\omega(s)+\text{dist}_{H}(s,v)$) in
$\widetilde{O}(|\partial{\text{Vor}}(s)|)$ time. But in [GKM+21, Section 7],
where this functionality is described, it is evident that within the same time
bound one can in fact aggregate over $\text{Vor}(s)$ (that is, compute the
maximum or e.g., sum) arbitrary vertex labels $\ell(v)$ (which could even
dependent on $s$; as long as they are computable in
$\widetilde{O}(|H|\cdot|\partial{H}|^{2})$ total additional time). Therefore,
if we assign the label $1$ to every vertex of $H$, in
$\widetilde{O}(|\partial{\text{Vor}}(s)|)$ time one can compute
$|\text{Vor}(s)|$. Through all $s\in|\partial{H}|$, this is
$\widetilde{O}(|\partial{H}|)$ time as mentioned before. ∎

For each piece $P$, besides the certificate $X_{P}$, we additionally maintain
a data structure $\mathcal{AV}_{P}$ of Theorem 6.2 for a ’’proxy‘‘
$P^{\prime}$ obtained from $P$ by removing all the vertices $v\in V(P)$
unreachable from $\partial{P}$. Observe that $\mathcal{AV}_{P}$ can be
computed in $\widetilde{O}(|P|\cdot(|\partial{P}|)^{2})=\widetilde{O}(r^{2})$
time. By Theorem 2.1, updating $\mathcal{R}$ along with all other associated
piecewise data structures costs $\widetilde{O}(r^{2})$ worst-case time.

Upon query about the number of vertices reachable from $s\in V$, we proceed as
follows. We first compute the subset $S\subseteq\partial{\mathcal{R}}$ of
boundary vertices reachable from $s$ in $G$ by running graph search from $s$
on the graph $P_{s}\cup X=P_{s}\cup\bigcup_{P\in\mathcal{R}}X_{P}$, where
$P_{s}$ is an arbitrarily chosen piece with containing $s$. This is correct by
Lemma 3.3 and costs $\widetilde{O}(r+n/\sqrt{r})$ time. From the graph search
we also retrieve the vertices $T\subseteq V(P_{s})\setminus\partial{P_{s}}$
that $s$ can reach. Then, for each $P\neq P_{s}$ we construct a weight
function $\omega_{P}$ such that if $\partial{P}\cap
S=\\{a_{1},\ldots,a_{k}\\}$ and $\partial{P}\setminus
S=\\{b_{1},\ldots,b_{l}\\}$, then: $\omega(a_{i}):=i\cdot M$ for all $i$ and
$\omega(b_{j}):=(k+j)\cdot M$ for all $j$, where $M=V(P)$. Note that since
$\text{dist}_{P^{\prime}}(\partial{P},v)<M$ for any $v\in V(P^{\prime})$, the
cell is uniquely determined for every $v\in V(P^{\prime})$. Namely, if $v$ can
be reached from $a_{i}\in\partial{P}\cap S$ in $P^{\prime}$, and $i$ is
minimized (and thus $s$ can reach $v$ through $S$), then
$v\in\text{Vor}(a_{i})$. Otherwise, $v$ can be reached from some
$b_{j}\in\partial{P}\setminus S$ in $P$, where $j$ is minimized (and $s$
cannot reach $v$ through $S$), and then $v\in\text{Vor}(b_{j})$. We conclude
that $\bigcup_{i=1}^{k}\text{Vor}(a_{i})$ contains precisely the vertices
$S_{P}\subseteq V(P)$ (including $\partial{P}\cap S$) that $s$ can reach via
paths through $\partial{P}$. By Theorem 6.2, their number
$|S_{P}|=\sum_{i=1}^{k}|\text{Vor}(a_{i})|$ can be computed in
$\widetilde{O}(\sqrt{r})$ time. In fact, these are _all_ vertices that $s$ can
reach in $P$: since $P\neq P_{s}$, either $s\notin V(P)$ or
$s\in\partial{\mathcal{R}}$, so every vertex in $P$ can be reached from $s$
only via some boundary vertex of $P$ anyway. We conclude that we can count
vertices reachable from $s$ in $G$ by computing:

$|S|+|T|+\sum_{P_{s}\neq
P\in\mathcal{R}}\left(|S_{P}|-|S\cap\partial{P}|\right).$

The query time is thus $\widetilde{O}(r+n/\sqrt{r})$. By picking $r=n^{2/5}$,
we make both the query time and the worst-case update time
$\widetilde{O}(n^{4/5})$.

## References

  * [AW14] Amir Abboud and Virginia Vassilevska Williams.  Popular conjectures imply strong lower bounds for dynamic problems.  In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, pages 434–443. IEEE Computer Society, 2014.
  * [BDP21] Aaron Bernstein, Aditi Dudeja, and Seth Pettie.  Incremental SCC maintenance in sparse graphs.  In 29th Annual European Symposium on Algorithms, ESA 2021, volume 204 of LIPIcs, pages 14:1–14:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [BFGT16] Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Robert E. Tarjan.  A new approach to incremental cycle detection and related problems.  ACM Trans. Algorithms, 12(2):14:1–14:22, 2016.
  * [BGS20] Aaron Bernstein, Maximilian Probst Gutenberg, and Thatchaphol Saranurak.  Deterministic decremental reachability, scc, and shortest paths via directed expanders and congestion balancing.  In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, pages 1123–1134. IEEE, 2020.
  * [BPW19] Aaron Bernstein, Maximilian Probst, and Christian Wulff-Nilsen.  Decremental strongly-connected components and single-source reachability in near-linear time.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pages 365–376. ACM, 2019.
  * [CHI+16] Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, Jakub Łącki, and Nikos Parotsidis.  Decremental single-source reachability and strongly connected components in õ(m$\surd$n) total update time.  In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, pages 315–324. IEEE Computer Society, 2016.
  * [CK22] Panagiotis Charalampopoulos and Adam Karczmarz.  Single-source shortest paths and strong connectivity in dynamic planar graphs.  J. Comput. Syst. Sci., 124:97–111, 2022.
  * [CKL+23] Li Chen, Rasmus Kyng, Yang P. Liu, Simon Meierhans, and Maximilian Probst Gutenberg.  Almost-linear time algorithms for incremental graphs: Cycle detection, sccs, $s$-$t$ shortest path, and minimum-cost flow, 2023.
  * [DS07] Krzysztof Diks and Piotr Sankowski.  Dynamic plane transitive closure.  In Algorithms - ESA 2007, 15th Annual European Symposium, Proceedings, pages 594–604, 2007.
  * [EFL18] Jeff Erickson, Kyle Fox, and Luvsandondov Lkhamsuren.  Holiest minimum-cost paths and flows in surface graphs.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 1319–1332, 2018.
  * [FR06] Jittat Fakcharoenphol and Satish Rao.  Planar graphs, negative weight edges, shortest paths, and near linear time.  J. Comput. Syst. Sci., 72(5):868–889, 2006.
  * [Fre85] Greg N. Frederickson.  Data structures for on-line updating of minimum spanning trees, with applications.  SIAM J. Comput., 14(4):781–798, 1985.
  * [Fre87] Greg N. Frederickson.  Fast algorithms for shortest paths in planar graphs, with applications.  SIAM J. Comput., 16(6):1004–1022, 1987.
  * [Gab00] Harold N. Gabow.  Path-based depth-first search for strong and biconnected components.  Inf. Process. Lett., 74(3-4):107–114, 2000.
  * [GKM+21] Pawel Gawrychowski, Haim Kaplan, Shay Mozes, Micha Sharir, and Oren Weimann.  Voronoi diagrams on planar graphs, and computing the diameter in deterministic õ(n${}^{\mbox{5/3}}$) time.  SIAM J. Comput., 50(2):509–554, 2021.
  * [GMWW18] Pawel Gawrychowski, Shay Mozes, Oren Weimann, and Christian Wulff-Nilsen.  Better tradeoffs for exact distance oracles in planar graphs.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 515–529. SIAM, 2018.
  * [GRST21] Gramoz Goranci, Harald Räcke, Thatchaphol Saranurak, and Zihan Tan.  The expander hierarchy and its applications to dynamic graph algorithms.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 2212–2228. SIAM, 2021.
  * [HdLT01] Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup.  Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity.  J. ACM, 48(4):723–760, 2001.
  * [HHK+23] Shang-En Huang, Dawei Huang, Tsvi Kopelowitz, Seth Pettie, and Mikkel Thorup.  Fully dynamic connectivity in o(log n(loglog n)${}^{\mbox{2}}$) amortized expected time.  TheoretiCS, 2, 2023.
  * [HKM+12] Bernhard Haeupler, Telikepalli Kavitha, Rogers Mathew, Siddhartha Sen, and Robert Endre Tarjan.  Incremental cycle detection, topological ordering, and strong component maintenance.  ACM Trans. Algorithms, 8(1):3:1–3:33, 2012.
  * [HKNS15] Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak.  Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture.  In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, pages 21–30. ACM, 2015.
  * [IKŁS17] Giuseppe F. Italiano, Adam Karczmarz, Jakub Łącki, and Piotr Sankowski.  Decremental single-source reachability in planar digraphs.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 1108–1121. ACM, 2017.
  * [IP01] Russell Impagliazzo and Ramamohan Paturi.  On the complexity of k-sat.  J. Comput. Syst. Sci., 62(2):367–375, 2001.
  * [Kle05] Philip N. Klein.  Multiple-source shortest paths in planar graphs.  In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, pages 146–155, 2005.
  * [KMNS17] Haim Kaplan, Shay Mozes, Yahav Nussbaum, and Micha Sharir.  Submatrix maximum queries in monge matrices and partial monge matrices, and their applications.  ACM Trans. Algorithms, 13(2):26:1–26:42, 2017.
  * [KMS13] Philip N. Klein, Shay Mozes, and Christian Sommer.  Structured recursive separator decompositions for planar graphs in linear time.  In Symposium on Theory of Computing Conference, STOC‘13, Palo Alto, CA, USA, June 1-4, 2013, pages 505–514, 2013.
  * [KS98] Philip N. Klein and Sairam Subramanian.  A fully dynamic approximation scheme for shortest paths in planar graphs.  Algorithmica, 22(3):235–249, 1998.
  * [KS23] Adam Karczmarz and Marcin Smulewicz.  On fully dynamic strongly connected components.  In 31st Annual European Symposium on Algorithms, ESA 2023, September 4-6, 2023, Amsterdam, The Netherlands, volume 274 of LIPIcs, pages 68:1–68:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023\.
  * [LP21] Yaowei Long and Seth Pettie.  Planar distance oracles with better time-space tradeoffs.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 2517–2537. SIAM, 2021.
  * [Łą13] Jakub Łącki.  Improved deterministic algorithms for decremental reachability and strongly connected components.  ACM Trans. Algorithms, 9(3):27:1–27:15, 2013.
  * [RZ08] Liam Roditty and Uri Zwick.  Improved dynamic reachability algorithms for directed graphs.  SIAM J. Comput., 37(5):1455–1471, 2008.
  * [San05] Piotr Sankowski.  Subquadratic algorithm for dynamic shortest distances.  In Computing and Combinatorics, 11th Annual International Conference, COCOON 2005, Kunming, China, August 16-29, 2005, Proceedings, volume 3595 of Lecture Notes in Computer Science, pages 461–470. Springer, 2005.
  * [Sha81] M. Sharir.  A strong-connectivity algorithm and its applications in data flow analysis.  Computers & Mathematics with Applications, 7(1):67–72, 1981.
  * [Sub93] Sairam Subramanian.  A fully dynamic data structure for reachability in planar digraphs.  In Algorithms - ESA ‘93, First Annual European Symposium, Bad Honnef, Germany, September 30 - October 2, 1993, Proceedings, pages 372–383, 1993.
  * [Tar72] Robert Endre Tarjan.  Depth-first search and linear graph algorithms.  SIAM J. Comput., 1(2):146–160, 1972.
  * [Tho04] Mikkel Thorup.  Compact oracles for reachability and approximate distances in planar digraphs.  J. ACM, 51(6):993–1024, 2004.
  * [vdBNS19] Jan van den Brand, Danupon Nanongkai, and Thatchaphol Saranurak.  Dynamic matrix inverse: Improved algorithms and matching conditional lower bounds.  In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, pages 456–480. IEEE Computer Society, 2019.
  * [Wil05] Ryan Williams.  A new algorithm for optimal 2-constraint satisfaction and its implications.  Theor. Comput. Sci., 348(2-3):357–365, 2005.
  * [Wul13] Christian Wulff-Nilsen.  Faster deterministic fully-dynamic graph connectivity.  In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 1757–1769. SIAM, 2013.