Decremental Single-Source Reachability in Planar Digraphs
Giuseppe F. Italiano∗1 , Adam Karczmarz†2 ,
Jakub Łącki‡3 , and Piotr Sankowski§2
1

University of Rome Tor Vergata, Italy
giuseppe.italiano@uniroma2.it

arXiv:1705.11163v1 [cs.DS] 31 May 2017

2

University of Warsaw, Poland
{a.karczmarz|sank}@mimuw.edu.pl
3

Google Research, New York, USA
jlacki@google.com

Abstract
In this paper we show a new algorithm for the decremental single-source reachability problem in
directed planar graphs. It processes any sequence of edge deletions in O(n log2 n log log n) total time
and explicitly maintains the set of vertices reachable from a fixed source vertex. Hence, if all edges
are eventually deleted, the amortized time of processing each edge deletion is only O(log2 n log log n),
√
which improves upon a previously known O( n ) solution. We also show an algorithm for decremental
maintenance of strongly connected components in directed planar graphs with the same total update
time. These results constitute the first almost optimal (up to polylogarithmic factors) algorithms for
both problems.
To the best of our knowledge, these are the first dynamic algorithms with polylogarithmic update
times on general directed planar graphs for non-trivial reachability-type problems, for which only
polynomial bounds are known in general graphs.

∗ Partly supported by the Italian Ministry of Education, University and Research under Project AMANDA (Algorithmics
for MAssive and Networked DAta).
† Supported by the Polish National Science Center grant number 2014/13/B/ST6/01811.
‡ This work was done when the author was partly supported by the EU FET project MULTIPLEX no. 317532, the
Google Focused Award on ”Algorithms for Large-scale Data Analysis” and Polish National Science Center grant number
2014/13/B/ST6/01811. Part of this work was done while Jakub Łącki was visiting the Simons Institute for the Theory of
Computing.
§ Supported by Polish National Science Center grant number 2014/13/B/ST6/01811. Part of this work was done while
Piotr Sankowski was visiting the Simons Institute for the Theory of Computing.

1

1

Introduction

The design of dynamic graph algorithms and data structures is one of the classical areas in theoretical
computer science. Dynamic graph algorithms are designed to answer queries about a given property
while the underlying graph is subject to updates, such as inserting or deleting a vertex or an edge. A
dynamic algorithm is said to be incremental if it handles only insertions, decremental if it handles only
deletions, and fully dynamic if it handles both insertions and deletions. Typically, one is interested in
very small query times (either constant or polylogarithmic), while minimizing the update times, whereas
the ultimate goal is to have both query and update times either constant or polylogarithmic. This
quest for obtaining polylogarithmic time algorithms has been so far successful only in few cases. Indeed,
efficient dynamic algorithms with polylogarithmic time per update are known only for few problems,
and are mostly limited to undirected graphs, such as dynamic connectivity, 2-connectivity, minimum
spanning tree and maximal matchings (see, e.g., [4, 23, 24, 25, 30, 43, 47, 51]). On the other hand,
dynamic problems on directed graphs are notoriously harder.1 For example, the fastest algorithms for
basic dynamic problems like reachability and transitive closure, have only polynomial times per update
(see, e.g., [9, 31, 41, 42]). Similarly, polynomial algorithms are only known for dynamic shortest paths
that do not seem to be easier on undirected graphs than on directed ones [8, 31, 49].
In this paper we consider the decremental single-source reachability problem, in which we are given
a directed graph G and a source node s and the goal is to maintain the set of vertices that are reachable
from vertex s, subject to edge deletions. Differently from undirected graphs, where polylog amortized
bounds per update have been known for more than one decade even in the fully dynamic setting (see,
e.g., [47]), for directed graphs there has been very limited progress on this problem. In fact, up until few
years ago, the best known algorithm for decremental single-source reachability had O(1) query time and
O(mn) total update time (i.e., O(n) amortized time per update if all edges are deleted). This bound was
simply achieved with Even-Shiloach trees [14], and it stood for over 30 years. In a recent breakthrough,
Henzinger et al. [21] presented a randomized decremental single-source reachability algorithm with total
update time O(mn0.984+o(1) ), which they later improved to O(mn0.9+o(1) ) [22]. Very recently, Chechik
e √n ).
et al. [7] improved the total update time to O(m
A closely related problem to decremental single-source reachability is decremental strong connectivity,
where we wish to answer queries of the form: “Given two vertices x and y, do x and y belong to the
same strongly connected component?”, subject to edge deletions. This problem is known to be almost
equivalent to decremental single-source reachability (see e.g., [7, 21, 41]), and the randomized algorithm
by Chechik et al. [7] can solve also decremental strong connectivity in constant time per query and
e √n ) amortized time per update, over any sequence of Ω(m) deletions. Again, the undirected version
O(
of this problem can be solved much faster, i.e., in polylog amortized time per update, even in the fully
dynamic setting [47]. Motivated by the limited progress on some dynamic graph problems, in their
seminal work Abboud and Vassilevska-Williams [2] proved conditional polynomial lower bounds, based
on popular conjectures, on several dynamic problems, including dynamic shortest paths, dynamic singlesource reachability and dynamic strong connectivity.
Similar situation holds even for planar graphs where dynamic problems have been studied extensively,
see e.g. [3, 11, 12, 13, 18, 19, 27, 34, 36, 37, 38, 44]. Despite this effort, the best known algorithms for
some basic problems on planar graphs, such as dynamic shortest paths and decremental single-source
reachability, still have polynomial update time bounds. For instance, for dynamic shortest paths on
e 2/3 ) amortized [15, 16, 27, 29, 32]. Very recently,
planar graphs the best known bound per operation is O(n
Abboud and Dahlgaard [1] proved polynomial update time lower bounds for dynamic shortest paths on
planar graphs, again based on popular conjectures. In particular, they showed that obtaining O(n1/2− )
bounds, for any  > 0, for dynamic shortest paths on planar graphs would yield a breakthrough for the
all-pairs shortest paths problem in general graphs. Quite surprisingly, this lower bound almost matches
the best running times for two related problems: dynamic reachability [11] and dynamic approximate
e √n).
shortest paths [3]. Hence, it might seem that the final answer to these problems is O(
Moreover, no polynomially faster algorithms are known even for decremental single-source reachability
on general planar graphs. The algorithm by Łącki [34] solves
both decremental single-source reachability
√
and decremental strong connectivity in a total of O(n n ) time, under any sequence of edge deletions.
1 The only exception being incremental single-source reachability that has trivial constant amortized update and query
algorithm.

1

e √n ) bound on general graphs [7].
Note that this bound is only logarithmic factors away from the O(m
Only in the very restricted case of st-planar graphs, i.e., planar acyclic digraphs with exactly one source
and exactly one sink, it was known for more than two decades how to solve the dynamic reachability
problem in O(log n) time per query and update [45, 46], provided that the edge insertions do not violate
the embedding of the st-planar graph.
e √n ) time barrier for directed problems on planar
In this paper, we break through the natural O(
graphs and present new decremental single-source reachability and decremental strong connectivity algorithms for planar graphs with total update time of O(n log2 n log log n), i.e., in O(log2 n log log n)
amortized time per update, over any sequence of Ω(n) deletions,
√ and O(1) time per query. This result
not only improves substantially the previously best known O(n n ) bound [34], but it also constitutes the
first almost optimal (up to polylog factors) algorithm for those problems. To the best of our knowledge,
our result is the first nontrivial dynamic algorithm for reachability problems on directed planar graphs
with polylog update bound. We hope that this result will pave a way for obtaining polylogarithmic
algorithms for dynamic directed problems on planar and possibly even general graphs.
Overview. Our improved algorithms for decremental single-source reachability and decremental
strongly connected components are based on several new ideas and techniques. First, we explore in
a somewhat non-traditional way the relation between primal and dual graph. Indeed, in Section 3, we
show a formal reduction from decremental single-source reachability to the switch-on reachability problem that we introduce. In the switch-on reachability problem we are given a directed graph, where all
edges are initially off and can be switched on in a dynamic fashion. The goal is to maintain, for each
edge uw, whether there is a path from w to u that consists solely of edges that are on.
In Section 4, we analyze the structural properties of a reachability matrix of a set of vertices2 that,
roughly speaking, lie on a constant number of simple faces, i.e., faces bounded with a single simple
cycle. We call such a matrix a face reachability matrix. The matrix viewpoint allows us to obtain
properties that are algorithmically useful and otherwise not easy to capture using the previously used
separating path approach to reachability in planar digraphs [11, 44, 48]. Those results are instrumental
for designing a novel algorithm that can incrementally maintain the transitive closure of a graph defined
by the union of two face reachability matrices that undergo incremental updates. This algorithm is
described in Section 5 and is perhaps one of the the key technical achievements of this paper.
In order to solve the switch-on reachability problem, we combine the algorithm of Section 5 with
a recursive decomposition of a planar graph G, which is a tree-like hierarchy of subgraphs of a graph
G (pieces) built by recursively partitioning G with small separators. For each piece H, the size of the
boundary ∂H of H (i.e. the set of vertices of H shared with pieces that are not descendants of H) is small.
Moreover, we require the boundary of H to lie on a constant number of faces of H. Such decompositions
proved very useful in obtaining near-linear planar graph algorithms, e.g., [5, 27, 35, 37], as well as
dynamic planar graph algorithms [11, 15, 40]. For each piece H of the decomposition, we dynamically
maintain the face reachability matrix of the set ∂H in both H and its complement G − (H − ∂H). The
idea of maintaining the information about the complements of the pieces of the decomposition has been
used previously [5, 35, 40]. However, to the best of our knowledge, in our paper this idea is used for the
first time in a dynamic setting. Moreover, we observe that in order to benefit from the Monge property
of paths in the complement G − (H − ∂H), the bounding cycles of faces constituting the boundary of
H have to be simple. Unfortunately, none of the state-of-the-art recursive decomposition algorithms
[5, 33] produces decompositions with such a property. To overcome this issue, in Section 2 we propose an
improved recursive decomposition that guarantees this property by possibly extending the input graph G.
We believe that this issue has been overlooked in the previous works that used the Monge property for
complements of pieces [5, 35, 40]. Finally, Section 6 puts all the ingredients together to obtain our
O(n log2 n log log n) time algorithm for the switch-on reachability problem.
Our result can be further extended to decrementally maintain the maximal (wrt. inclusion) 2-edgeconnected subgraphs of a planar digraph. For C ⊆ V , an induced subgraph G[C] is 2-edge-connected
iff it is strongly connected and contains no edges whose removal would make G[C] no longer strongly
connected. The 2-edge-connectivity in digraphs has been often studied in recent years (see e.g., [6,
17, 20]). In particular, the static computation of the maximal 2-edge-connected subgraphs proved to
2 A reachability matrix of a set S is a submatrix of the transitive closure matrix consisting of rows and columns
corresponding to vertices belonging to S.

2

be a challenging task. The best known bounds for general digraphs are O(n2 ) for dense graphs [20]
and O(m3/2 ) for sparse graphs [6]. We show that for planar digraphs, the maximal 2-edge-connected
subgraphs can be computed in O(n log2 log log n) time. Moreover, they can be maintained subject to
edge deletions within the same total time bound.
Another extension is an incremental transitive closure algorithm, in which the embedding of the final
graph is given upfront. In other words, we are given a directed planar graph in which all edges are
off, each update operation switches some edge on and the goal is to answer reachability queries with
respect to the edges that are currently on. We note that the same “switch-on” model
was considered
e √n) time, and any
in [19] for undirected reachability. The reachability queries are answered in O(
sequence of updates is handled in O(n log2 n log log n) time. This result shows that progress can be made
also in the case of incremental planar graph transitive closure. Moreover, it pinpoints the hardness of
incremental planar graphs problems, where few results have been obtained so far, as it is not known how
to incrementally maintain small separators.

2

Preliminaries

Let G = (V, E) be a graph. We let V (G) and E(G) denote the vertex and edge set of G, respectively.
Assume that G is a directed graph (digraph). A set of vertices S ⊆ V is strongly connected if there is a
path in G between every two vertices of S. A strongly connected component (SCC) of G is a maximal
(w.r.t. inclusion) strongly connected subset of vertices.
Throughout, we use the term planar digraph to denote a directed planar multigraph. In particular,
we allow the digraphs to have parallel edges and self-loops. Formally, there might exist multiple edges
e1 , e2 , . . ., such that each ei connects the same pair of vertices u, v ∈ V . We use the notation uv ∈ E
to denote any of the edges uv, whereas when we write uv = e ∈ E, we mean some specific edge e going
from u to v.
Even though we allow the graphs not to be simple, we assume throughout the paper that |E| =
O(|V |). This is justified by the fact that in the problems we solve, self-loops and parallel edges can be
ignored. However, parallel edges and self-loops might arise as we transform our problem. To simplify
the presentation, we do not prune them, but instead guarantee that at any time the number of edges
remains linear in the number of vertices.
Let e ∈ E(G). We denote by G − e the graph obtained from G by removing e and by G/e the graph
obtained by contracting e.
G
/ w to denote a directed path from u
Finally, if G is a directed graph and u, w ∈ V (G), we use u
to w in G. The graph is sometimes omitted, if it is clear from the context.
Planar Graph Embeddings and Duality. We provide intuitive definitions below. For formal definitions, see e.g. [10]. An embedding of a planar graph is a mapping of its vertices to distinct points and
of its edges to non-crossing curves in the plane. We say that a planar graph G is plane embedded (or
plane, in short), if some embedding of G is assumed. The face of a connected plane G is a maximal open
connected set of points that are not in the image of any vertex or edge in the embedding of G. There is
exactly one unbounded face.
The bounding cycle of a bounded (unbounded, resp.) face f is a cycle consisting of edges bounding f
in clockwise (counterclockwise, resp.) order. Here, we ignore the directions of edges. The face is called
simple if and only if its bounding cycle is a simple cycle.
By the Jordan Curve Theorem, a Jordan curve C partitions R2 \ C into two connected regions, a
bounded one B and an unbounded one U . We say that a set of points P is strictly inside (strictly
outside, resp.) C, if and only if P ⊆ B (P ⊆ U , resp.). P is weakly inside (weakly outside, resp.) if and
only if P ⊆ B ∪ C (P ⊆ U ∪ C, resp.).
Let G = (V, E) be a plane embedded planar digraph. The dual graph of G, denoted by G∗ , is a plane
directed graph, whose set of vertices is the set of faces of G. Moreover, for each edge uw = e ∈ E(G),
G∗ contains a directed edge from the face left of e (looking from u in the direction of w) to the face right
of e. We denote this edge in the dual as e∗ .
We use the fact that removing an edge in the primal graph corresponds to contracting its dual edge
in the dual graph. Formally:

3

Fact 2.1. (G − e)∗ = G∗ /e∗ .
Let G be a directed graph. We say that uw = e ∈ E is an inter-SCC edge if u and w belong to
distinct SCCs of G, and an intra-SCC edge otherwise. Note that uw is an inter-SCC edge iff there is no
path from w to u in G. In our algorithm we use the following relation.
Lemma 2.2 (folklore, see e.g. [28]). Let G be a plane embedded digraph and e ∈ E(G). Then, e is an
inter-SCC edge of G iff e∗ is an intra-SCC edge of G∗ .
Subgraphs, etc. Let G = (V, E) be a plane (directed or undirected) graph. A plane graph G0 =
(V 0 , E 0 ) is called a subgraph of G if V 0 ⊆ V and E 0 ⊆ E 0 . G0 inherits the embedding of G. For a subset
F ⊆ E we define an edge-induced subgraph G[F ] to be a subgraph (VF , F ) of G such that VF is the set
of endpoints of the edges F .
For two graphs G1 = (V1 , E1 ), G2 = (V2 , E2 ), we define their union G1 ∪ G2 as the graph (V1 ∪
V2 , E1 ∪ E2 ). Analogously, we define the intersection G1 ∩ G2 as the graph (V1 ∩ V2 , E1 ∩ E2 ).
Let H be a subgraph of G. We define a hole of H a face of H that is not a face of G. A simple hole
is a hole of H that is a simple face of H.
Planar Graph Decompositions. Let G = (V, E) be a connected, undirected plane graph. Let
n = |V |. A recursive decomposition of G is a collection of connected, edge-induced subgraphs of G
organized in a binary tree T (G). We write H ∈ T (G) to denote that H, which is a subgraph of G, is a
node of T (G). The level of H ∈ T (G) is defined as the number of edges on the path from the root to
H. The tree T (G) has the following properties:
• The root of T (G) is the graph G itself.
• A non-leaf subgraph H ∈ T (G) has exactly two children child1 (H), child2 (H) such that child1 (H)∪
child2 (H) = H.
• We define the set of boundary vertices of a subgraph H ∈ T (G) (denoted by ∂H) inductively:
– If H is the root of T (G), that is, H = G, then ∂H = ∅.

– Otherwise, let P and S be the parent and the sibling of H in T (G), resp. Then ∂H =
V (H) ∩ (V (S) ∪ ∂P ).

• Each H ∈ T (G) has O(1) holes and all vertices of ∂H lie on the holes of H.
√
• If i is the level of H, then |∂H| = O( n/ci ), for some c > 1.
P
2
•
H∈T (G) |∂H| = O(n log n).
• There are O(n) leaf subgraphs in T (G) and each leaf subgraph has O(1) edges.
• T (G) has O(log n) levels.
Remark 2.3. The definition of a recursive decomposition naturally extends to directed plane graphs.
However, each H ∈ T (G) is connected in the undirected sense, i.e., weakly-connected.
Corollary 2.4. Let T (G) be a recursive decompositionP
of a plane graph G = (V, E). Then each e ∈ E
is contained in some leaf subgraph of T (G). Moreover, H∈T (G) |E(H)| = O(n log n).
Definition 2.5. We call a recursive decomposition T (G) simple if and only if for each H ∈ T (G):
1. the holes of H are all simple and vertex-disjoint,
2. if H has a sibling S in T (G), then E(H) ∩ E(S) = ∅.
An algorithm for building a recursive decomposition of an n-vertex planar graph in O(n log n) time
essentially follows from [5, 33]. However, these decompositions do not guarantee that the holes are
simple, which is essential when using “external” reachability matrices. In Sections 6 and 8 we show how
a planar graph G can be augmented into a graph G0 so that G0 has a simple recursive decomposition
and all the interesting reachability properties of G are preserved in G0 . Both the augmentation and the
decomposition can be computed in O(n log n) time.
4

Problem Definitions. This paper deals with two decremental graph problems. In both problems the
input is a digraph and the goal is to design a data structure that supports two operations. The first
operation deletes a given edge from G. The second operation is a query operation and its meaning is
problem-dependent.
In the decremental strongly connected components (decremental SCC) problem the query operation
is given two vertices u, w ∈ V (G) as parameters. The goal is to determine whether u and w are in the
same SCC of G.
In the decremental single-source reachability (decremental SSR) problem a source vertex s ∈ V (G) is
given in the input in addition to the graph G. Each query operation has a vertex v ∈ V (G) as parameter
G
/ v.
and asks to determine whether there exists a path s
The efficiency measure of such data structures is the total time needed to process all edge deletions.
Unless stated otherwise, the queries are answered in constant time.

3

The Switch-On Reachability Problem

The core part of our algorithm solves the following problem, which we call switch-on reachability problem.
The input is a digraph G = (V, E). Each edge of this digraph is either on or off. Initially, each edge is
of G off and an update operation may turn an edge on. Turning edges off is not allowed. The goal is to
maintain, for each edge uw of G (regardless of whether it is on or off), whether there is a directed path
from w to u consisting solely of edges that are on. Note that since turning edges off is not allowed, once
such a path appears, it may never disappear.
We first show that the decremental SCCs problem in planar digraphs can be reduced to the switch-on
reachability problem.
Lemma 3.1. Assume there exists an algorithm for the switch-on reachability problem in planar digraphs.
Then, there exists an algorithm that maintains the set of inter-SCC edges of a planar digraph under edge
deletions with the same asymptotic running time and space usage.
Proof. Consider a digraph G subject to edge deletions. Our goal is to maintain the set of inter-SCC
edges in G. By Lemma 2.2, it suffices to maintain the set of intra-SCC edges in G∗ . Recall that when G
undergoes deletions, G∗ is subject to edge contractions (see Fact 2.1). To reduce to switch-on reachability,
we build a graph H such that (i) edge contractions in G∗ can be simulated by switch-on operations on
H, and (ii) H preserves the reachability information of G∗ (i.e., for any pair of vertices x and y, there is
a path from x to y in G∗ if and only if there is a path from x to y in H consisting of edges that are on).
We do this as follows. Let H = (V (G∗ ), E(G∗ ) ∪ E R (G∗ )) where E R (G∗ ) is the set of reverse edges,
containing a unique edge e∗R = wu for each edge uw = e∗ ∈ E(G∗ ). To initialize H, we start from all
edges switched off, and then switch on all the edges in E(G∗ ). Note that, after this preprocessing, H
trivially preserves the reachability information of G∗ .
When an edge e is deleted from G and consequently its dual edge e∗ is contracted in G∗ , we update H
by switching on the reverse edge e∗ R . As a result, G∗ contains a single vertex created by the contraction,
while H contains two vertices that are mutually adjacent (through edges that are on). Thus, throughout
the sequence of updates (i.e., contractions in G∗ and switch-on operations in H), H keeps preserving the
reachability information of G∗ .
Recall that an edge e = uw of G∗ is an intra-SCC edge iff there exists a path from w to u in G∗ . This
in turn happens if there is a path from w to u in H, as e is also an edge of H and it is always switched on.
In order to test this condition, we can run the algorithm for the switch-on reachability problem on H.
The algorithm maintains whether the endpoints of every edge are connected with a directed path. This
allows us to maintain the set of intra-SCC edges in G∗ , which in turn gives the desired set of inter-SCC
edges in G.
We next analyze the running time. Building G∗ takes linear time. Initializing H takes linear time,
plus the time required to switch on all the edges in E(G∗ ). Moreover, each edge deletion in G can be
translated to a corresponding operation of the algorithm for switch on-reachability in constant time, as
we can precompute pointers between the corresponding edges of G, G∗ and H. Indeed, the edges of
G∗ map to the edges of H in a natural way, as G∗ is a minor of H (i.e., G∗ can be obtained from H
by deleting and contracting edges). Thus, the running time and the space usage are dominated by the
algorithm for switch-on reachability.
5

Lemma 3.2. Assume there exists an algorithm that maintains the set of inter-SCC edges of a planar
digraph under edge deletions. Then, there exists an algorithm for the decremental SCC problem in planar
digraphs with the same asymptotic total running time and space usage. The query time of the decremental
SCC algorithm is constant.
Proof. Let G be a planar digraph subject to edge deletions. Define Ḡ to be the undirected graph obtained
from G by first removing inter-SCC edges and then ignoring edge directions. Observe that the connected
components of Ḡ are exactly the same as the SCCs of G. Thus, to determine if two vertices are strongly
connected in G it suffices to check if they are in the same connected component of Ḡ.
Observe that if uv is an inter-SCC edge of G, then uv is an inter-SCC edge in any subgraph of G that
contains it. Thus, once an edge becomes an inter-SCC edge in G, it remains an inter-SCC edge until it
is deleted.
The algorithm maintaining inter-SCC edges of G allows us to maintain Ḡ: whenever e becomes an
inter-SCC edge in G, it is deleted from Ḡ. Thus, edges may only be deleted from Ḡ. As a result, we can
use the decremental connectivity algorithm of Łącki and Sankowski [38] to maintain the connected components of Ḡ. This allows us to answer connectivity queries in Ḡ, and, consequently, strong connectivity
queries in G. The total update time of the decremental connectivity algorithm is linear and each query
is answered in constant time. Thus, the update and query times and the space usage of the resulting
algorithm are asymptotically the same as in the algorithm maintaining inter-SCC edges.
Remark 3.3. The paper of Łącki and Sankowski [38] also describes an algorithm that explicitly maintains
the set of vertices in each connected component and runs in O(n log n) time. By using their algorithm,
we can obtain a decremental SCC algorithm that not only supports queries in constant time, but also
explicitly maintains the set of vertices in each SCC.
Moreover, a decremental SCC algorithm implies an algorithm for decremental single-source reachability. In general graphs, this follows from a very simple reduction (see e.g., [7]). However, this reduction
does not preserve planarity, so we need to provide a slightly more complicated one.
Lemma 3.4. Assume there exists an algorithm for decremental SCC problem in planar digraphs that
explicitly maintains the set of vertices in each SCC and runs in Ω(n log n) time. Then, there exists an
algorithm for decremental single-source reachability problem in planar digraphs with the same asymptotic
total update time, query time and space usage.
Proof. A condensation of a directed graph G, denoted by cond(G), is a graph obtained from G by
contracting all its SCCs. The vertices of cond(G) are sets of vertices of G contained in the corresponding
SCC. Note that cond(G) is a directed acyclic graph (DAG).
Our goal is to maintain the set of vertices of cond(G), which are reachable from the vertex of cond(G)
containing the source vertex s. The high-level idea is that in order to maintain SCCs of G we use the
decremental SCC algorithm, whereas to maintain the set of reachable vertices in cond(G) we use the fact
that it is a DAG, which makes the problem much easier.
We first describe a simple dynamic single-source reachability algorithm for DAGs. This algorithm
maintains the set of vertices reachable from a fixed source and supports two types of updates. The first
update removes a single edge, whereas the second one replaces a vertex v with an acyclic subgraph H.
This happens in three steps. First, some number of new vertices are added to the maintained graph G
(vertex v is not deleted). Second, some edges of G, whose endpoint is v may change this endpoint to one
of the newly added vertices. Third, new edges can be added, but their endpoints can only be the newly
added vertices and v. Also, adding these edges may not introduce cycles.
Note that both operations are in a sense decremental, as once a vertex becomes unreachable from
the source, it never becomes reachable again. The set of vertices reachable from the source can be easily
maintained by iteratively applying the following principle: if a vertex distinct from the source has no
incoming edges, it is not reachable from the source and thus can be deleted from G. The resulting
algorithm runs in time which is linear in the size of the original graph and the number of vertices and
edges added in the course of the algorithm. See [34] for details.
It remains to describe how to maintain cond(G) and funnel the updates to cond(G) to the dynamic
single-source reachability algorithm for DAGs. We run the decremental SCC algorithm that maintains
the SCCs explicitly (see Remark 3.3). Whenever an inter-SCC edge of G is deleted, it has a corresponding
edge in cond(G) and to update cond(G) it suffices to remove this corresponding edge. Otherwise, if an
6

intra-SCC edge is removed from an SCC C, the SCC may decompose into SCCs C1 , . . . , Ck . Wlog.
assume that C1 is the largest one of these SCCs. Thus, to update cond(G) we add one new vertex for
each of C2 , C3 , . . . , Ck . We do not need to add a vertex corresponding to C1 , as we update the vertex
corresponding to C (reuse it), so that it represents C1 . Some edges that were incident to C need to be
updated, as after the edge deletion their endpoint is one of C2 , . . . , Ck . In order to do that, we iterate
through all edges of G incident to vertices contained in C2 , . . . , Ck . Similarly, by iterating through all
these edges we may add all new inter-SCC edges that appear as a result of the edge deletion.
It follows that the total running time of the algorithm is dominated by the initial graph size and
the total time of iterating through edges in the process of handling an edge deletion. An edge uw is
considered only when the size of the SCC containing either u or w halves. Thus, we spend O(log n) time
for each edge, which gives O(n log n) total time.

4

Structural Properties of Reachability in Plane Digraphs

In this section we present the structural properties of reachability in planar digraphs that we later
exploit in our algorithms. We show how to efficiently represent reachability information between a set of
vertices that, roughly speaking, lie on a constant number of faces. In fact, our analysis is more general
and extends to sets of vertices that lie on a constant number of separator curves, which we define below.
In the following definition, we consider undirected graphs or directed graphs where edge directions are
ignored.
Definition 4.1. Let G be a plane embedded graph. A Jordan curve C is a separator curve of G if and
only if one of the following holds:
1. each connected component of G lies either weakly inside C or strictly outside C;
2. each connected component of G lies either weakly outside C or strictly inside C.
Moreover, for each e ∈ E(G), the interior of (the embedding of ) e is either a contiguous fragment of C
or is disjoint with C.
We will sometimes abuse the notation and identify the separator curve with the set of vertices lying
on it.
Fact 4.2. Let f be a cycle bounding some simple face of a plane embedded graph G. Then, the closed
curve defined by the embedding of f is a separator curve.
Consider a plane digraph G and let U = U1 ∪ . . . ∪ U` be a set of vertices of G that lie on ` = O(1)
pairwise disjoint separator curves C1 , . . . , C` of G. We have Ui = U ∩ Ci , which implies Ui ∩ Uj = ∅ for
i 6= j. We define a total order ≺ on the elements of U , which satisfies the following property. Consider
the sequence S(U ) of elements of U sorted according to ≺. Then, elements of each Ui form a contiguous
fragment of S(U ) and are sorted in clockwise order. There could be multiple total orders that satisfy
this property. Namely, for each Ui the smallest vertex with respect to ≺ can be chosen arbitrarily and
the contiguous fragments corresponding to sets U1 , . . . , U` may come in any order. However, this is not
relevant to our later analysis. Thus, in the following, we assume that each set U has an associated total
order ≺. For X, Y ⊆ U we also write X ≺ Y if for each x ∈ X, y ∈ Y , we have x ≺ y. Note that X ≺ Y
implies X ∩ Y = ∅.
Definition 4.3. Let A be a binary matrix with both its rows and columns indexed with the vertices
of U = U1 ∪ . . . ∪ U` , such that the sets Ui lie on ` pairwise disjoint separator curves C1 , . . . , C` of
G, respectively. The rows and columns of A are ordered according to the order ≺ induced by the sets
U1 , . . . , U` . We say that A is a reachability matrix for U if and only if for each u, v ∈ U , Au,v = 1 if
G
/ v.
and only if there exists a path u
In the following we fix the sequences U1 , . . . , U` and C1 , . . . , C` and the order ≺ satisfying the assumption of Definition 4.3. We set U = U1 ∪ . . . ∪ U` .

Definition 4.4. Let X, Y ⊆ U and let A be the reachability matrix of U . A binary matrix AX,Y with rows
indexed with X and columns indexed with Y is called a reachability submatrix for X, Y iff AX,Y
x,y = Ax,y
X
X,X
for all x ∈ X and y ∈ Y . Also, denote by A the matrix A
.
7

Definition 4.5. Let X, Y ⊆ U . The subset of Y containing those y such that for some x ∈ X, AX,Y
x,y = 1
is called the set of active columns of AX,Y and is denoted by act(AX,Y ).
Definition 4.6. For a set A = {AS1 ,T1 , . . . , ASk ,Tk } of reachability submatrices and a row s ∈ V , we
define a row projection rπs (A) to be the subset {ASj ,Tj ∈ A : s ∈ Sj }. Similarly, for t ∈ V , we define a
column projection cπt (A) = {ASj ,Tj ∈ A : t ∈ Tj }.
The following lemma provides a decomposition of the reachability matrix A = AU used in the next
sections in a black-box manner.
Lemma 4.7. Let G be a plane embedded digraph and let C1 , . . . , C` be pairwise disjoint separator curves
of G, where ` = O(1). Let U be a subset of V (G) of size m such that U = U1 ∪ . . . ∪ U` and the vertices
of Ui lie on Ci .
Then, the reachability matrix A of U in G can be partitioned into a set A = {AS1 ,T1 , . . . , ASk ,Tk } of
reachability submatrices such that:
1. for each s, t ∈ U , s 6= t, there exists exactly one such ASj ,Tj ∈ A that s ∈ S and t ∈ T ,
0

2. for each ASj ,Tj ∈ A and T 0 = act(ASj ,Tj ), the ones in each row of AS,T form O(1) blocks,
3. for any s ∈ U and t ∈ U , the sets rπs (A) and cπt (A) have size O(log m).
The sets Sj and Tj that define the partition do not depend on the entries of AUi . The partition A can
be computed in O(m2 ) time.
The remaining part of the section is devoted to proving Lemma 4.7.
Definition 4.8. The reachability submatrix AS,T is called bipartite, if S and T lie on a single separator
curve (i.e., S, T ⊆ Ui for i ∈ {1, . . . , `}) and either S ≺ T or T ≺ S.
Lemma 4.9 (Monge property). Let AS,T be a bipartite reachability submatrix of U . Let a, b ∈ S and
S,T
S,T
S,T
c, d ∈ T be such that a ≺ b and c ≺ d. Suppose AS,T
a,c = 1 and Ab,d = 1. Then Aa,d = 1 and Ab,c = 1
also hold.
Proof. We have S, T ⊆ Ui for some i. Without loss of generality, assume that S ≺ T and that all
connected components of G lie either weakly inside of Ci or strictly outside Ci . Since a, b, c, d lie on Ci ,
the connected components of G containing any of these vertices are all weakly inside Ci . As AS,T
a,c = 1,
G
/ c contained entirely weakly inside Ci . Similarly, there exists a
there exists a simple path P = a
G
/
path Q = b
d contained weakly inside Ci . By planarity of G, we conclude that the paths P and Q
must have a common vertex w (see Figure 1). Note that w is reachable from both a and b. Analogously,
G
/ d and b G / c.
both c and d are reachable from w. Thus, there also exist paths a

X1

a

d

X2

Ci
w
T

X1

AX1 ,X2

S
c

X2

b
Figure 1

AX2 ,X1

Figure 2

8

Lemma 4.10. Let AS,T be a bipartite reachability submatrix of U . Let T 0 = act(AS,T ). Denote by
0
t1 ≺ . . . ≺ tp the elements of T 0 . For each non-zero row s of AS,T , the ones in that row form a single
0
contiguous block, i.e., there exist ls and rs (1 ≤ ls ≤ rs ≤ p) such that AS,T
= 1 holds if and only if
s,t
t ∈ {tls , . . . , trs }.
0

Proof. Let s ∈ S be some row of AS,T containing at least one non-zero entry. Suppose there exist
0
S,T 0
S,T 0
0
a, b, c ∈ T 0 such that a ≺ b ≺ c and AS,T
s,a = 1, As,b = 0 and As,c = 1. By the definition of T , there
0

0
exists some other row s0 ∈ S, s0 6= s, such that AS,T
s0 ,b = 1. Wlog. assume s ≺ s . Thus, we have both
0

0

0

S,T
S,T
AS,T
s,a = 1 and As0 ,b = 1. By Lemma 4.9 this implies As,b = 1, a contradiction.

Lemma 4.11. Let Ui be a set of vertices lying on a single separator curve in G and m = |Ui |. The reachability submatrix AUi can be partitioned into a set AUi = {AS1 ,T1 , . . . , ASk ,Tk } of bipartite reachability
submatrices such that:
1. for each s, t ∈ Ui , s 6= t, there exists exactly one such ASj ,Tj ∈ AUi that s ∈ Sj and t ∈ Tj ,
2. for any s ∈ Ui and t ∈ Ui , the sets rπs (AUi ) and cπt (AUi ) have size O(log m).
The sets Sj and Tj that define the partition do not depend on the entries of AUi . The partition AUi can
be computed in O(m2 ) time.
Proof. We give a recursive procedure to construct the partition AX , for X ⊆ Ui . If |X| = 1, the
procedure exits immediately. Otherwise, let X = {x1 , . . . , xk }, where x1 ≺ . . . ≺ xk and k ≥ 2. Let
q = b(k + 1)/2c. Set X1 = {x1 , . . . , xq } and X2 = {xq+1 , . . . , xk }. Note that X1 ≺ X2 . Thus, both
AX1 ,X2 and AX2 ,X1 are bipartite reachability submatrices. We add these matrices to the partition and
recurse on the subsets X1 and X2 (see Figure 2).
Note that for any s, t ∈ Ui , s 6= t, the last recursive call with both s and t in the input set X places
Ui
X1 ,X2
i
the entries AU
and AX2 ,X1 .
s,t and At,s in the bipartite reachability submatrices A
Fix x ∈ X and assume |X| = k. Let f (k) be the number of bipartite reachability submatrices
that are produced by the recursive algorithm and contain a row (column) corresponding to x. We have
f (k) ≤ f (dk/2e) + 1 and thus it is easy to see that f (k) = O(log k). Thus, we conclude that for any s,
|rπs (AUi )| = O(log m) and similarly |cπs (AUi )| = O(log m).
The recursive procedure runs in time that is proportional to the total size of matrices that are
produced. Recall that for each s, t ∈ Ui , s 6= t, there exists exactly one such ASj ,Tj ∈ AUi that s ∈ Sj
and t ∈ Tj . It follows that the total running time is O(m2 ).
An analogue of Lemma 4.10 can be shown for reachability submatrices AUi ,Uj , where i 6= j.
Lemma 4.12. Let AS,T be a reachability submatrix for the sets S = Ui , T = Uj , where i 6= j. Let
0
T 0 = act(AS,T ). For each row s of AS,T , the ones in that row form O(1) connected blocks.
Proof. Let s be some row of AS,T containing at least one non-zero entry. Equivalently, there exists a
G
/ y for some y ∈ T . Without loss of generality, assume that all connected components of G
path s
lie either weakly inside Ci or strictly outside Ci . As s ∈ Ci and y is in the same connected component of
G as s, y lies weakly inside Ci . However, y ∈ Cj and Ci ∩ Cj = ∅, so entire Cj lies strictly inside Ci . In
particular, all vertices of T lie strictly inside Ci .
G
/ y be some shortest directed path from s to a vertex of T . Clearly, P is simple and y
Let P = s
is the only vertex of P ∩ T . Let q be the last vertex of P such that q ∈ S and denote by Q the directed
subpath q = v1 . . . vk = y of Q. By the definition of a separator curve, Q is weakly inside Ci , weakly
outside Cj and Q ∩ Ci = {q}, Q ∪ Cj = {y}.
Let G0 be obtained by “cutting” G along the path Q as follows. We split each vertex vi of Q into two
vertices vi0 and vi00 , that inherit the edges of vi strictly emanating left or right of Q, respectively. The
created vertices are connected with directed paths Q0 = v10 . . . vk0 and Q00 = v100 . . . vk00 (see Figure 3). Let
U ∗ = S ∪ T \ Q ∪ Q0 ∪ Q00 . Note that all the vertices of U ∗ lie on a single separator curve C ∗ of G0 . This
curve imposes some clockwise order on U ∗ .
First we prove that any t ∈ T \ {y} is reachable from q in G if and only if t is reachable from either
G
0
/ t and let z be the last vertex
q or q 00 in G0 . The “if” part is trivial. Suppose there is a path R = q
9

S
s

s
y 0 y 00

vk = y
vk−1
P

T

P

Q

0
vk−1

00
vk−1

Q0

Q00

v20

v2
v1 = q

v200
q 0 q 00

Figure 3
that R and Q have in common. Note that z is not the last vertex of R and let the edge going out of
/ t of R only shares its starting point with Q and thus
z emanate (wlog.) left of R. The subpath z
0
0
G0
G
/ t. Therefore, there exists a path q 0 G / z 0 −→
corresponds to a path z 0
t.
Next we prove that for s 6= q, any t ∈ T \ {y} is reachable from s in G if and only if t is reachable
from either q 0 or q 00 or s in G0 . To see the “if” part, note that t is reachable from q 0 or q 00 in G0 iff it
is reachable from q in G, whereas q is reachable from s in G. For the “only if” part, suppose there is a
G
/ t. Either this path intersects with Q and then t is reachable from q in G (which implies that
path s
t is reachable from q 0 or q 00 in G0 ), or the path does not intersect with Q and is thus preserved in G0 .
Now let S ∗ = S \ {q} ∪ {q 0 , q 00 } and T ∗ = T \ {y}. Observe that the sets S ∗ , T ∗ constitute contiguous
fragments of the cycle containing the elements of U ∗ ordered clockwise around C ∗ . Consider the bipartite
∗
∗
∗
∗
reachability matrix AS ,T of the graph G0 . We show that act(AS,T ) = act(AS ,T ) ∪ {y}. Clearly,
∗
∗
G
/ x, where x ∈ T \ {y}. If
act(AS ,T ) ∪ {y} ⊆ act(AS,T ). Let x ∈ act(AS,T ). There exists a path S
0
this path does not intersect with Q, then it also exists in G . Otherwise, x is reachable from q in G and
thus is reachable from either q 0 or q 00 in G0 .
∗
∗0
∗
∗
By Lemma 4.10, the ones in each row of AS ,T , where T ∗ 0 = act(AS ,T ) form at most one block.
∗
∗0
Now let B be the matrix AS ,T but with columns ordered according to the order imposed on T . As
the order of T ∗ is just a cyclical shift of the order of T \ {y}, we conclude that for each row of B, the
ones in that row form O(1) blocks of columns. To finish the proof, observe that the ones in the row s of
0
AS,T can be seen as as the sum of:
• a single one in the column y (as y ∈ T 0 ),
• the ones in the row q 0 of B,
• the ones in the row q 00 of B,
• if s 6= q, the ones in the row s of B,
which clearly make up at most O(1) blocks of ones in the row s.
Proof of Lemma 4.7. We first partition A into `2 reachability submatrices AUi ,Uj , for all i, j ∈ {1, . . . , `}.
Each AUi ,Ui is then partitioned using Lemma 4.11, whereas each AUi ,Uj , for i 6= j, is included in
A without further partitioning. As each u ∈ U belongs to exactly one Ui , |rπu (A)| = |cπu (A)| =
O(log |Ui |) + ` − 1 = O(log m). By Lemmas 4.10 and 4.12, for all AS,T ∈ A, the ones in each row of
0
0
S,T
AS,T , where
P T =2 act(A 2), form at most O(1) connected blocks. The running time of this procedure
2
is O(m + i |Ui | ) = O(m ).

10

5

The Switch-On Monge Transitive Closure

Let G1 and G2 be two plane embedded digraphs and let Ui ⊆ V (Gi ) be a set of vertices lying on
a constant number of pairwise disjoint separator curves of Gi , for i = 1, 2. Moreover, assume that
V (G1 ) ∩ V (G2 ) ⊆ U1 ∩ U2 .
In this section we consider the following problem. Assume that the edges of G1 and G2 undergo
switch-on operations. Denote by Gi the subgraph of Gi consisting of the edges that are switched on.
This way, the entries of the reachability matrix Ai of Ui in Gi may change from 0 to 1. We wish to
maintain the reachability matrix A = AU1 ∪U2 of the graph G1 ∪ G2 subject to updates to the matrices
A1 and A2 . Note that our assumptions imply that A depends only on A1 and A2 .
Observe that as Gi is a subgraph of Gi , the separator curves of Gi are also the separator curves of
Gi . The remaining part of this section is devoted to proving the following theorem.
Theorem 5.1. Let Ui be a set of vertices lying on a constant number of separator curves of Gi (for
i = 1, 2), such that V (G1 ) ∩ V (G2 ) ⊆ U1 ∩ U2 . Let m = |U1 ∪ U2 |. Assume that the edges of Gi
undergo switch-ons and denote by Gi the subgraph of Gi consisting of the edges that are on. Let Ai be
the reachability matrix of Ui in Gi and let A be the reachability matrix of U1 ∪ U2 in G1 ∪ G2 . Suppose
that after a switch-on we are given the list of entries in A1 and A2 that changed. Then we can initialize
and maintain the matrix A in O(m2 log m log log m) total time.

5.1

Queue-Based Incremental Transitive Closure Algorithm

We first show and analyze a simple queue-based algorithm for updating the transitive closure of a
graph after a set of edges is added. Its pseudocode is given as Algorithm 1. The algorithm should be
considered folklore, but for sake of completeness we describe it in a detailed way, as we need its efficient
implementation.
The transitive closure algorithm is based on the following idea. Whenever it determines that a vertex
b is reachable from a vertex a, it infers that every vertex reachable from b by an edge is also reachable
from a and every vertex that has an edge to a can also reach b. Then, it propagates this information
using a queue. In the pseudocode, we use Out(b) to denote the set of heads of out-edges of b and In(a)
to denote the set of tails of in-edges of a. Moreover, Unreachable(a, A) is the set of vertices x such that
Aa,x = 0 and CannotReach(b, A) is the set of vertices x such that Ax,b = 0.
Algorithm 1 The queue-based incremental transitive closure.
Input: A digraph G, such that E + ⊆ E(G) and the transitive closure A of G − E + .
Ensure: A is the transitive closure of G.
1: function UpdateTransitiveClosure(G, A, E + )
2:
Q := empty queue
3:
for uw ∈ E + do
4:
if Au,w = 0 then
5:
Au,w := 1
6:
Q.Enqueue(uw)
7:
while Q is not empty do
8:
ab := Q.Dequeue
9:
for x ∈ Out(b) ∩ Unreachable(a, A) do
10:
Aa,x := 1
11:
Q.Enqueue(ax)
12:
for x ∈ In(a) ∩ CannotReach(b, A) do
13:
Ax,b := 1
14:
Q.Enqueue(xb)

Lemma 5.2. Algorithm 1 is correct.
Proof. We first show that the algorithm sets Ap,q = 1 We use induction on k. For each k ≥ 1 we show
that at the beginning of the k-th iteration of the while loop:
11

1. Ap,q = 1 only if there is a path from p to q in G,
2. Q only contains pairs pq such that Ap,q = 1.
The second item follows directly from the pseudocode. To show the first one, observe that the algorithm
sets Aa,x = 1 in line 10 when Aa,b = 1 (since ab has been removed from Q) and bx ∈ E(G). Similarly,
it sets Ax,b = 1 when Aa,b = 1 and xa ∈ E(G). In both cases the induction hypothesis implies that the
underlying paths exist. This completes the first part of the proof.
It remains to show that if adding E + causes q to be reachable from p, then the algorithm sets Ap,q = 1
G
/ q. We say that an edge
(we assume that q was not reachable from p before adding E + ). Let P = p
+
e of P has a detour avoiding E if a subpath of P containing e can be replaced with a path (detour) that
does not contain edges of E + and the obtained path still connects p and q. As long as P has an edge
of E + that has a detour avoiding E + we replace its respective subpath with the detour. This process
terminates, as at each step we reduce the number of edges of E + on P . Once the process terminates,
P contains some edge uw of E + , as there is no path from p to q that does not contain edges of E + .
Moreover, uw does not have a detour avoiding E + .
G
/ q 0 be a subpath of P that contains the edge uw. We have that Ap0 ,q0 = 0 before the
Let P 0 = p0
algorithm was run. We now use induction on the length of P 0 to show that the algorithm sets Ap0 ,q0 = 1.
The case when k = 1 is easy, because the only valid path P 0 of length 1 contains the edge uw by
itself. Let us now consider a path P 0 of length k > 1. Either the first or the last edge of P 0 is not equal
to uw. Without loss of generality, let us assume that it is the last one and denote it by rq 0 . By the
induction hypothesis, the algorithm sets Ap0 ,r = 1. This means that it then adds p0 r to the queue.
Consider the iteration of the while loop when p0 r is removed from the queue, that is ab = p0 r.
Clearly, q 0 ∈ Out(b) = Out(r), as rq 0 is an edge on a path in G. There are two cases to consider. If
q 0 6∈ Unreachable(a, A) = Unreachable(p0 , A), then Ap0 ,q0 = 1, so the procedure has already set Ap0 ,q0 = 1.
Otherwise, q 0 ∈ Unreachable(a, A) and then Ap0 ,q0 = 1 is set in line 10 of some iteration of the for-loop.
This completes the proof.
The following lemma highlights which part of Algorithm 1 can be sped up.
Lemma 5.3. The running time of Algorithm 1, excluding the time needed to compute the sets Out(b) ∩
Unreachable(a, A) and In(a) ∩ CannotReach(b, A), is proportional to the number of entries of A that are
changed from 0 to 1 (or constant, if no entries are changed).
Proof. Let k be the total number of entries of A that are changed from 0 to 1 by the algorithm. Observe
that just before the algorithm sets Aa,x := 1 in line 10, we have Aa,x = 0, as x ∈ Unreachable(a, A). The
similar reasoning applies to line 13. Thus, the total running time of the two for loops is proportional
to k.
Moreover, the number of elements added to the queue Q is at most k. This implies that the total
number of iterations of the while loop is at most k, and the lemma follows.

5.2

Proof of Theorem 5.1

Our goal is to maintain the transitive closure of a matrix that is given as a bitwise OR of matrices A1
and A2 . The following notation will prove useful in the remainder of the paper.
Definition 5.4. Let M be some binary matrix with rows and columns indexed with a vertex set VM . Let
EM = {uv : u, v ∈ VM ∧ Mu,v = 1}. We denote by G(M ) the graph (VM , EM ).
Using this notation, our goal is to maintain the transitive closure of a graph H = G(A1 ) ∪ G(A2 ).
The vertex set of H is U1 ∪ U2 . Note that as the entries of A1 , A2 change only from zero to one, the set
E(H) undergoes incremental updates.
In order to handle each update efficiently, we use Algorithm 1. Moreover, we leverage the special structure of these matrices to reduce the total time spent on computing the sets Out(b) ∩ Unreachable(a, A)
and In(a) ∩ CannotReach(b, A) in lines 9 and 12. In the following we only deal with the former set; in
order to compute the latter, one needs to proceed symmetrically.
We first describe how the algorithm represents the matrices A1 and A2 and updates their representation. Let us focus on A1 , as the representation of A2 is analogous. The algorithm uses Lemma 4.7 to
compute the partition A1 = {AS1 ,T1 , . . . , ASk ,Tk }. For each AS,T ∈ A1 it maintains the following:
12

• the contents of the matrix AS,T ,
• the set act(AS,T ),
• for each row s of AS,T , the set Outs (AS,T ) = {x : AS,T
s,x = 1}.
0

Let T 0 = act(AS,T ). By Lemma 4.7, the ones in each row of AS,T form O(1) contiguous blocks. Thus,
internally the set Outs (AS,T ) is represented by a constant number of intervals. We have that AS,T
s,x = 1
S,T
iff x ∈ act(A ) and x belongs to one of the intervals.
Lemma 5.5. The representation of matrices of A1 and A2 can be computed and maintained in O(m2 log m)
total time throughout any sequence of updates to A1 and A2 .
Proof. For simplicity, let us consider A1 . By Lemma 4.7, we can compute A1 in O(m2 ) time. Observe
that, by Lemma 4.7, this partition is independent of the values in the cells of A1 , so it does not need to
be updated.
Whenever a cell of A1 changes from 0 to 1 we update the corresponding cell in some ASi ,Ti . Note that,
again by Lemma 4.7, for each cell of A1 there is exactly one AS,T ∈ A1 that contains the corresponding
cell. We can compute the mapping between the cells while computing A1 , so the values in the matrices
from A1 can be updated in constant time. While updating the matrices, it is also easy to update the set
act(AS,T ) for each AS,T ∈ A1 .
It remains to describe how to maintain Outs (AS,T ) for each row s of AS,T . Consider a sequence
obtained from this row by removing cells in inactive columns. We store this sequence in a balanced
binary tree, keyed by the column. This tree can be updated in O(log m) time when a column becomes
active or some cell changes its value from 0 to 1. Moreover, it can be easily augmented so as to maintain
the O(1) intervals that we use to represent Outs (AS,T ).
There is a small technicality here. Each update to A1 may consist of multiple cells changing value
from 0 to 1 and only after all cells have been updated the structural properties of Lemma 4.7 hold. Thus,
before all cells in the considered row are updated, the representation of Outs (AS,T ) may consist of more
than a constant number of intervals, which could affect the running time. However, this does not pose
an issue, as we can force the binary tree to compute only the first O(1) intervals of the representation.
As a result, the running time is not affected and the representation is correct once all entries of A1 are
updated.
Updating the matrices and the sets act(AS,T ) takes time which is linear in the size of A1 , that is
O(m2 ). To bound the running time of updating the sets Outs (AS,T ) we note that each element is inserted
into the binary tree only once (when the corresponding column becomes active) and can be updated only
once (when the corresponding matrix entry changes value from 0 to 1). Thus, we spend O(log m) time
for each cell of each AS,T ∈ A1 . This gives O(m2 log m) time in total, and yields the lemma.
For each a ∈ U1 ∪ U2 and AS,T ∈ A1 ∪ A2 the algorithm stores a reachability candidates set
cana (AS,T ) ⊆ act(AS,T ).
The algorithm maintains the invariant that cana (AS,T ) =
act(AS,T ) ∩ Unreachable(a, A). Whenever a column t ∈ T of AS,T becomes active, we check whether
Aa,t = 0 and if this is the case, we insert t into cana (AS,T ). Once we set Aa,t = 1, t is removed
from cana (AS,T ) (and, clearly, never added again, as Aa,t will never change its value back to 0). Each
cana (AS,T ) is stored as a dynamic predecessor data structure, such as the van Emde Boas tree [50].
Lemma 5.6. The sets of reachability candidates can be updated in O(m2 log m log log m) total time.
Proof. Fix a ∈ U1 ∪ U2 . For each AS,T ∈ A1 ∪ A2 each element of T is added to and removed from
cana (AS,T ) at most once. If A1 ∪ A2 = {AS1 ,T1 , . . . , ASk ,Tk } then the total number of operations is
Pk
each b ∈ U1 ∪ U2 there are O(log m) matrices AS,T ∈ A1 ∪ A2 such that
i=1 |Ti |. By Lemma 4.7, for P
k
b ∈ T . Thus we make at most i=1 |Ti | = O(m log m) operations for a fixed a, which gives O(m2 log m)
operations in total. Since each operation on a van Emde Boas tree takes O(log log m) time, we conclude
that maintaining reachability candidates takes O(m2 log m log log m) time.
We are now ready to show how to speed up line 9 of Algorithm 1. The goal is to compute the set
Out(b) ∩ Unreachable(a, A) efficiently. Algorithm 1 traverses this set, once it is computed, but this does
not affect the running time considerably. Only the computation of the set could be slow. This means

13

that it suffices to compute the set in time which is, say, almost linear in its size. Our algorithm, roughly
speaking, uses the property that Out(b) is represented by a small number of intervals, so computing an
intersection with the set Out(b) is easy. Recall that rπb (Ai ) is the subset of Ai consisting of matrices
which contain the row b.
Lemma 5.7. Let
Q=

[

[

i∈{1,2} AS,T ∈rπb (Ai )


cana (AS,T ) ∩ Outb (AS,T ) .

Then Q = Out(b) ∩ Unreachable(a, A).
Proof. By Lemma 4.7 and the definition of the sets Outb (AS,T ), we have
[
[
Outb (AS,T )
Out(b) =
i∈{1,2} AS,T ∈rπb (Ai )

=

[

[

i∈{1,2} AS,T ∈rπb (Ai )

act(AS,T ) ∩ Outb (AS,T ).

Moreover cana (AS,T ) = act(AS,T ) ∩ Unreachable(a, A). Hence
[
[
Q=
cana (AS,T ) ∩ Outb (AS,T )
i∈{1,2} AS,T ∈rπb (Ai )

=

[
i∈{1,2}
AS,T ∈rπb (Ai )

act(AS,T ) ∩ Unreachable(a, A) ∩ Outb (AS,T )

= Out(b) ∩ Unreachable(a, A).
Lemma 5.8. Q = Out(b) ∩ Unreachable(a, A) can be computed in O(|Q| log log m + log m) time.
Proof. By Lemma 5.7, it suffices to compute
[
[
i∈{1,2} AS,T ∈rπb (Ai )

cana (AS,T ) ∩ Outb (AS,T ).

Since |rπb (Ai )| = O(log m) (by Lemma 4.7), this is a sum of O(log m) sets of the form cana (AS,T ) ∩
Outb (AS,T ). Moreover, these sets are disjoint since for the matrices AS,T such that AS,T ∈ rπb (Ai ), the
sets T are disjoint.
Let us focus on computing cana (AS,T ) ∩ Outb (AS,T ). Recall that Outb (AS,T ) is represented as a
constant number of intervals, such that x ∈ Outb (AS,T ) iff x belongs both to act(AS,T ) and one of the
intervals. However, we also have cana (AS,T ) ⊆ act(AS,T ). As a result, to compute the intersection it
suffices to take elements of cana (AS,T ) that are contained in the intervals describing Outb (AS,T ). Since
cana (AS,T ) is represented as a van Emde Boas tree, finding a single element of cana (AS,T ) contained in
a given interval can be done in O(log log m) time. Thus, we spend O(log log m) time on computing each
element of Q plus O(log m) time to consider O(log m) sets that comprise the sum.
Proof of Theorem 5.1. By Lemmas 5.5 and 5.6 the total cost of computing and updating the representations of A1 and A2 and the reachability candidates is O(m2 log m log log m). By Lemma 5.3, the total
running time of Algorithm 1 excluding the cost of lines 9 and 12 is O(m2 ). By Lemma 5.8, it takes
O(q log log m + log m) to execute each of these lines, assuming that they compute a set of size q. Since
each such set is then traversed by the algorithm, the O(q log log m + log m) = O((q + 1) log m) overhead
implies that the transitive closure algorithm runs in O(m2 log m) total time. Thus, the overall running
time is O(m2 log m log log m).

6

The Switch-On Reachability Data Structure

In this section we show how to combine the recursive decomposition tree with the switch-on transitive
closure data structure of Theorem 5.1 in order to solve efficiently the switch-on reachability problem.
14

By Lemmas 3.1 and 3.2, this will imply an algorithm for solving the decremental strongly-connected
components problem within the same time bounds.
Let G = (V, E) be a plane embedded digraph and let n = |V |. The following technical lemma is
proved in Section 8.
Lemma 6.1. Let G = (V, E) be a planar digraph and let n = |V |. In O(n log n) time we can construct
a plane digraph G0 = (V 0 , E 0 ) along with:
• a simple recursive decomposition T (G0 ),
• two disjoint subsets E0 , E1 ⊆ E 0 ,
• a 1-to-1 mapping S from V to the set of strongly connected components of (V 0 , E0 ),
• a bijective function p : E → E1 ,
satisfying the following properties.
1. |V 0 | = O(n) and |E 0 | = O(n).
2. The are no inter-SCC edges in (V 0 , E0 ).
3. For any uv = e ∈ E, let u0 v 0 = p(e) ∈ E1 . Then u0 ∈ S(u) and v 0 ∈ S(v).
Corollary 6.2. Let G = (V, E). Let G0 = (V 0 , E 0 ), E0 , E1 , S and p be defined as in Lemma 6.1.
/ v 0 exists in
Let u0 , v 0 ∈ V 0 and let u0 ∈ S(u) and v 0 ∈ S(v). Then for any F ⊆ E, a path u0
0
/ v exists in (V, F ).
(V , E0 ∪ p(F )) if and only if a path u
Proof. The proof is trivial when u = v, so suppose u 6= v.
Let π = v0 , e1 , v1 , . . . , vk−1 , ek , vk be a simple path in (V 0 , E0 ∪ p(F )), where v0 = u0 and vk = v 0 .
For x ∈ V 0 , denote by s(x) the unique vertex of V such that x ∈ S(s(x)). Let ei1 , . . . , ei` be the
edges of π ∩ p(F ) in order of their occurrence on π. As for all edges vj vj+1 of E0 lying on π we have
s(vj ) = s(vj+1 ) (recall that (V 0 , E0 ) has no intra-SCC edges), we conclude that s(viq −1 ) = s(viq−1 ) for
any q = 2, . . . , `. We also have s(vi1 −1 ) = s(v0 ) = s(u0 ) and s(vi` ) = s(vk ) = s(v 0 ). Moreover, for each ij ,
/ s(v 0 ) in
p−1 (eij ) = s(vij −1 )s(vij ) = s(vij−1 )s(vij ). Thus, p−1 (ei1 )p−1 (ei2 ) . . . p−1 (ei` ) is a path s(u0 )
0
0
(V, F ). To conclude, note that s(u ) = u and s(v ) = v.
/ v in (V, F ), where ei = ui vi . Let u0 , v 0 be any vertices of V 0
Conversely, let e1 . . . ek be a path u
i i
0
0
such that ui ∈ S(ui ) and vi ∈ S(vi ). For each i = 2, . . . , k we have vi−1 = ui and thus there exists a path
0
/ u0 in (V 0 , E0 ). We now show that for each i there is also a path u0
/ v 0 in (V 0 , E0 ∪ p(ei )).
vi−1
i
i
i
0
0
Let p(ei ) = xi yi . Note that s(xi ) = s(ui ) and s(yi ) = s(vi ) and hence there is a path u0i → xi → yi → vi0
in (V 0 , E0 ∪ p(ei )).
We conclude that there is a path u01 → v10 → u02 → v20 → . . . u0k → vk0 in (V 0 , E0 ∪ p(F )).
The data structure presented in this section requires a simple recursive decomposition T (G). We
now prove that the general case of any planar digraph G can be reduced to the case when we are given
a simple recursive decomposition without increasing the overall asymptotic running time of the whole
algorithm.
Lemma 6.3. Let G be a planar digraph and let n = |V (G)|. In O(n log n) time we can reduce the
switch-on reachability problem on G to the switch-on reachability problem on a plane graph G0 with a
given simple recursive decomposition T (G0 ) and such that |V (G0 )| = O(n) and |E(G0 )| = O(n).
Proof. Let G0 = (V 0 , E 0 ) and p be defined as in Lemma 6.1. By definition, G0 is accompanied with a
simple recursive decomposition T (G0 ). Hence, we only need to show how to translate the updates to G
into the updates to G0 .
We first switch on all edges of E0 . When an edge e ∈ E of G is switched on, we switch on p(e) in G0 .
The edges of E 0 \ (E0 ∪ E1 ) are never switched on in G0 . Let F ⊆ E be the subset of edges of G that
are switched on at some point of time. For any uv = e ∈ E, let u0 v 0 = e0 = p(e). By Corollary 6.2, the
path v → u exists in (V, F ) iff the path v 0 → u0 exists in (V 0 , E0 ∪ p(F )). Thus, to track the reachability
between the endpoints of e, we only need to track the reachability between the endpoints of p(e). This
is done by solving the switch-on reachability problem on G0 .
15

In the remaining part of this section we assume that we are given a simple recursive decomposition
T (G) of G.
For H ∈ T (G), denote by G − H the edge-induced subgraph G[E \ E(H)].
Lemma 6.4. Let H ∈ T (G). Then V (H) ∩ V (G − H) ⊆ ∂H.
Proof. The proof is by induction of the level of H in T (G). If H is the root, then G − H is empty and
the statement is clearly true.
Consider now H which is not the root of T (G). Let P be the parent of H and assume V (P ) ∩ V (G −
P ) ⊆ ∂P . Let S be the sibling of H. Recall that, by definition, ∂H = (V (H) ∩ ∂P ) ∪ (V (H) ∩ V (S)).
Let v ∈ V (H) ∩ V (G − H). Clearly, v ∈ V (P ) since E(H) ⊆ E(P ). Moreover, v is incident to at least
one edge e of E \ E(H). If e ∈ E \ E(P ), then v ∈ V (G − P ) and thus v ∈ ∂P ∩ V (H). Otherwise,
e ∈ E(S) and hence v ∈ V (S) ∩ V (H).
Lemma 6.5. Let H ∈ T (G). A cycle bounding a hole of H is a separator curve of H.
Proof. By Fact 4.2, the cycle bounding a simple face of H is a separator curve of H.
Lemma 6.6. Let H ∈ T (G). A cycle bounding a hole of H is a separator curve of G − H.
Proof. Note that the holes of H can be seen as unions of original faces of G, merged by removing the
edges of G−H from G. Thus, each edge of G−H lies inside some unique hole h of H. Let Eh ⊆ E(G−H)
be the subset of edges lying inside h.
Let Ch be the cycle bounding a hole h of H. Assume wlog. that h is a bounded face, then the inside of
Ch is the same as the inside of h (the case when h is unbounded is analogous; we replace each occurrence
of “inside of Ch ” with “outside of Ch ”). By Lemma 6.5, for each Ch , H lies weakly outside Ch . If h is the
only hole of H, then clearly G − H = G[Eh ] lies weakly on one side of Ch and the Lemma holds.
Assume now that h is not the only hole, and let h0 6= h be some other hole of H. As h0 and h are
disjoint, h0 lies strictly outside Ch . Thus, all edges of Eh0 lie strictly outside Ch . Hence, V (G[Eh ]) ∩
V (G[Eh0 ]) = ∅ for h0 6= h. To conclude, note that for each weakly connected component of G − H, the
edges of that component are contained in a unique subset Eh .
Remark 6.7. The assumption that T (G) is simple is crucial to proving Lemma 6.6, which does not hold
if the holes of H are not pairwise-disjoint or not necessarily simple.
Lemma 6.8. Let H ∈ T (G). The set ∂H can be partitioned into O(1) sets ∂1 H, . . . , ∂` H so that each
∂i H lies on a curve Ci such that Ci is a separator curve of both H and G − H.
Proof. Let h1 , . . . , h` be the holes of H. By Lemmas 6.5 and 6.6, we can set ∂i H to be the subset of ∂H
lying on hi . By the definition of T (G), each v ∈ ∂H lies on a unique hole of H.
Denote by G the subgraph of G consisting of the edges that are switched on. Our strategy will be to
maintain, for each leaf subgraph H ∈ T (G), a binary matrix R(H) with both rows and columns indexed
G
/ v. Recall that our goal is
with the vertices of H, such that R(H)u,v = 1 iff there exists a path u

G
/ u consisting of edges that are
to track, for each uv ∈ E, the information whether there is a path v
switched on. By the definition of T (G), each edge uv ∈ E is contained in some leaf subgraph H ∈ T (G)
and thus all the needed information is contained in the matrices R(·). To efficiently update the matrices
R(·) while the edges are switched on, we maintain two types of auxiliary information for each H ∈ T (G):

1. A binary matrix In(H) with both rows and columns indexed with the vertices of ∂H, such that
/ v in H ∩ G;
In(H)u,v = 1 iff u, v ∈ ∂H and there exists a path u
2. A binary matrix Ex(H) with both rows and columns indexed with the vertices of ∂H, such that
/ v in (G − H) ∩ G.
Ex(H)u,v = 1 iff u, v ∈ ∂H and there exists a path u
Additionally, for each leaf subgraph H we maintain the transitive closure of H ∩ G in a binary matrix
In∗ (H). Note that In(H) is a subgraph of In∗ (H), namely In(H) = In∗ (H)[∂H]. In the following we
discuss how the matrices In(·), Ex(·), In∗ (·) and R(·) interplay and we show how they can be efficiently
maintained for any sequence of edge switch-ons. Observe that all these matrices undergo monotone
changes: the edge switch-ons can only cause their entries to change from 0 to 1. Therefore, an m × m
matrix can be updated only O(m2 ) times.
16

Lemma 6.9. Let H be a leaf subgraph of T (G). In∗ (H) can be initialized and maintained in O(1) total
time subject to any sequence of switch-ons of edges of H.
Proof. As each leaf subgraph has constant size, once one of the O(1) edges of H is switched-on, the
matrix In∗ (H) can be recomputed from scratch in O(1) time.
In the following lemma we say that a matrix M depends only on some matrices M1 , . . . , Mk if the
information contained in M1 , . . . , Mk is sufficient to compute M .
Lemma 6.10. Let H be a subgraph of T (G) and let m = |∂H|.
1. If H is a leaf subgraph, then In(H) depends only on In∗ (H).
2. If H is a non-leaf subgraph, then In(H) depends only on In(child1 (H)) and In(child2 (H)).
3. If H is a non-root subgraph, then let P and S be the parent and the sibling of H in T (G), respectively. Ex(H) depends only on Ex(P ) and In(S).
4. If H is a leaf subgraph of T (G), then R(H) depends only on In∗ (H) and Ex(H).
Any of the matrices In(H), Ex(H), R(H) can be maintained in O(m2 log m log log m) total time subject
to any sequence of updates to the matrices it depends on.
The dependencies stated in Lemma 6.10 are depicted in Figure 4.
Proof. (1) In(H) is a submatrix of In∗ (H), which is of constant size. The total number of updates to
In∗ (H) is O(1).
(2) For i = 1, 2, set Gi = childi (H), Ui = ∂childi (H), and Ai = In(childi (H)). Note that by
Lemma 6.8, the set Ui lies on a constant number of separator curves Gi . We also have V (G1 ) ∩ V (G2 ) ⊆
U1 ∩ U2 and |U1 ∪ U2 | = O(|U1 | + |U2 |) = O(m). By Theorem 5.1, the reachability matrix A of U1 ∪ U2
in (child1 (H) ∪ child2 (H)) ∩ G can be maintained in O(m2 log m log log m) total time, subject to any
sequence of updates to A1 and A2 . As ∂H ⊆ ∂child1 (H) ∪ ∂child2 (H), In(H) is a submatrix of A and
thus can be maintained within the same time bounds.
(3) Set G1 = G − P , G2 = S, U1 = ∂P , U2 = ∂S, A1 = Ex(P ) and A2 = In(S). Note that by
Lemma 6.4, V (S) ∩ V (G − P ) ⊆ V (P ) ∩ V (G − P ) ⊆ ∂P and similarly V (S) ∩ V (G − P ) ⊆ V (S) ∩
V (G − S) ⊆ ∂S. Therefore, V (G1 ) ∩ V (G2 ) ⊆ U1 ∩ U2 . By Lemma 6.8, the set Ui lies on a constant
number of separator curves of Gi .
By Theorem 5.1, the reachability matrix A of U1 ∪ U2 in (G1 ∪ G2 ) ∩ G can be maintained in
O(m2 log m log log m), since |U1 ∪U2 | = O(|U1 |+|U2 |) = O(m). As E(H)∩E(S) = ∅ and E(H)∪E(S) =
E(P ), G1 ∪ G2 = (G − P ) ∪ S = G − H. Thus, A actually represents the reachability between vertices
∂P ∪ ∂S in G − H. As clearly ∂H ⊆ ∂P ∪ ∂S, Ex(H) is a submatrix of A and thus can be maintained
in O(m2 log m log log m) time as well.
/ v in the graph TH = G(In∗ (H)) ∪
(4) We show that R(H)u,v = 1 iff there exists a path u
G(Ex(H)) (see Definition 5.4). Note that V (TH ) = V (H).
TH
/ v, there
Clearly, by the definitions of the matrices In∗ (H) and Ex(H), if there exists a path u
also exists a path u

G

/ v.

G
/ v such that u, v ∈ V (H). Split P into maximal subpaths P1 , . . . , Pk
Now, let P be some path u
fully contained (as far as their edges are concerned) in either E(H) or E(G − H).
/ b entirely contained in G − H. Then a, b ∈ V (G − H). We prove that
Let Pi be a subpath a
a ∈ V (H). The proof that b ∈ V (H) is analogous. We either have i = 1 and a = u implies a ∈ V (H), or
the path Pi−1 is fully contained in H and thus a ∈ V (H) as well. Now, as a, b ∈ V (G − H) ∩ V (H), by
Lemma 6.4, we have a, b ∈ ∂H. Hence, there is an edge ab in G(Ex(H)).
H
/ b, there is an edge ab in G(In∗ (H)). We conclude that
By the definition of In∗ (H), for Pi = a
G
/ b, there is an edge ab ∈ E(TH ) and thus there is a path u TH / v.
for each subpath Pi = a
As each of the matrices In∗ (H), Ex(H) is of constant size and ` = O(1), the matrix R(H) encoding the
transitive closure of TH can be recomputed in O(1) time after any update to these matrices. Moreover,
the total number of changes to the matrices In∗ (H), Ex(H) is constant.

17

In(H1 )

G = H1

H2

H4

In(H2 )

H3

H5

H6

H7

In(H4 ) Ex(H4 )
In∗ (H4 )

R(H4 )

Ex(H1 )

Ex(H2 )

In(H3 )

In(H5 ) Ex(H5 )
In∗ (H5 )

R(H5 )

In(H6 ) Ex(H6 )
In∗ (H6 )

R(H6 )

Ex(H3 )

In(H7 ) Ex(H7 )
In∗ (H7 )

R(H7 )

Figure 4: An example decomposition T (G) (top) and the dependencies between the corresponding
matrices In(H), In∗ (H), Ex(H), R(H), for H ∈ T (G) (bottom).
Note that each matrixSdepends directly on at most two other matrices. The dependencies allow us
to organize the matrices H∈T (G) {In∗ (H), In(H), Ex(H), R(H)} in a dependency list L, such that each
matrix depends only on matrices earlier in the sequence. The order of the elements of L is as follows. The
matrices form groups according to their type. The order on groups is In∗ , In, Ex, R. Matrices within the
groups In∗ , In and R are sorted increasingly inclusion-wise by their corresponding subgraphs of T (G).
On the other hand, the matrices within the group Ex are sorted decreasingly inclusion-wise by their
corresponding subgraphs of T (G).
Lemma 6.11. Let G be a plane digraph and let n = |V (G)|. Let T (G) be a simple recursive decomposition
of G. The switch-on reachability problem on G can be solved in O(n log2 n log log n) time.
Proof. We initialize the data structures maintaining the matrices of the dependency list. When an edge
e is switched on, we create a priority queue Q of matrices that potentially need updates. The elements
of Q are keyed by their position in the list L. First, the unique matrix In∗ (H) such that e ∈ E(H), is
pushed to Q. We repeatedly pop matrices M out of Q and process either the edge switch-on (in the case
of In∗ (·) matrices) or the changes in matrices M 0 such that M directly depends on M 0 . If the matrix M
changes after switching e on, we push to Q all matrices M2 such that M2 directly depends on M . The
correctness of this update procedure follows form the fact that the dependencies do not form cycles and
all required matrices In∗ (·) are notified about the switch-on.
Observe that as for each matrix M ∈ L, there are at most two matrices of L that depend directly on
M , the total number of times a matrix is inserted to Q is proportional
to the total size of the matrices of
P
L plus the sum of sizes of the leaf subgraphs of T (G), i.e., O( H∈T (G) |∂H|2 + |E(H)|) = O(n log n), by
Corollary 2.4. Thus, the cost of priority queue operations is O(n log2 n). By Lemma 6.10 for H ∈ T (G),
the total time needed to initialize and maintain the matrices {In∗ (H), In(H), Ex(H), R(H)} subject to
2
2
the updates to
Pmatrices that2 they depend on, is O(|∂H| log |∂H| log log |∂H|) = O(|∂H| log n log log n).
Recall that
= O(n log n). Thus, the total cost over all subgraphs H ∈ T (G) is
H∈T (H) |∂H|
2
O(n log n log log n).
Theorem 6.12. Let G be a planar digraph and let n = |V (G)|. The switch-on reachability problem on
G can be solved in O(n log2 n log log n) time.
Proof. We first apply Lemma 6.3 to reduce the problem to the case with a given simple recursive decomposition T (G). The reduction takes O(n log n) time. Then, we apply Lemma 6.11.

7
7.1

Extensions of the Switch-On Reachability Data Structure
Computing Maximal 2-Edge Connected Subgraphs

Definition 7.1. Let G = (V, E) be a digraph. We call an edge e ∈ E a strong bridge of G iff G − e has
more strongly connected components than G.

18

Lemma 7.2. Let G be a plane digraph and let uv = e ∈ E(G) be an intra-SCC edge of G. Let
/ b in G∗ − e∗ .
ab = e∗ ∈ E ∗ . The edge e is a strong bridge of G iff there exists a path a

/ a in G∗ .
Proof. By Lemma 2.2, e∗ is an inter-SCC edge of G∗ , or equivalently, there is no path b
Note that e is a strong bridge iff some edge f ∈ E \ {e} is intra-SCC in G but is inter-SCC in G − e.
Equivalently, by Fact 2.1, f ∗ is inter-SCC in G∗ and is intra-SCC in G∗ /e∗ . Consequently, there is a
set of edges C ⊆ E(G∗ /e∗ ), f ∈ C, such that C forms a directed cycle in G∗ /e∗ , but does not form a
directed cycle in G∗ . Thus, C is in fact a directed path a → b in G∗ . However, e∗ ∈
/ C, and hence the
lemma follows.
Lemma 7.3. Let G be a planar digraph and let n = |V |. The set of strong bridges of G can be maintained
subject to edge deletions in O(n log2 n log log n) total time.
Proof. Similarly as in the proof of Lemma 3.1, we reduce our problem to maintaining the graph G+ =
(V (G∗ ), E(G∗ ) ∪ E R (G∗ )) under edge switch-ons. A contraction of e in G∗ is translated to a switch-on of
eR in G+ . By Lemma 7.2, it is sufficient to solve the following extended switch-on reachability problem
on the input graph G+ . Given a planar digraph H, we need to maintain for each edge of uv = e ∈ E(H)
/ v in H − e, where H is an incremental, switched-on subgraph of H.
whether there is a path u
The next step is to reduce such an extended switch-on reachability problem to the case when the
underlying graph has a simple recursive decomposition T (H). To this end, we apply Lemma 6.1 to H
and obtain the graph H 0 = (V 0 , E 0 ), function p and the subsets E0 , E1 ⊆ E 0 . Analogously as in the
proof of Lemma 6.3, the edges E0 are switched on during the initialization, the edges E 0 \ (E0 ∪ E1 )
are never switched-on, whereas a switch-on of the edge e ∈ E(H) is translated to a switch-on of p(e)
/ v exists in
in H 0 . Note that, by Corollary 6.2, for any F ⊆ E(H), and any uv = e ∈ H, a path u
0
0
0
0
/
(V (H), F \ {e}) if and only if a path u
v exists in (V , E0 ∪ p(F \ {e})) = (V , E0 ∪ p(F ) \ {p(e)}),
where p(e) = u0 v 0 . Hence, in order to maintain the reachability between the endpoints of e in H − e we
only need to maintain the reachability between the endpoints of p(e) in H 0 − p(e). Recall that the cost
of applying Lemma 6.1 is O(n log n) and the size of the obtained graph H 0 is linear in the size of H.
Therefore, to finish the proof, we only need to solve our extended switch-on reachability problem on a
graph H having a simple recursive decomposition T (H).
To this end, we extend the data structure of Section 6 as follows. Recall that, by the simplicity of
T (H), for each edge e ∈ H there is a unique leaf subgraph L ∈ T (H) containing e. Also recall that
the reachability information between the vertices of L in H can be recomputed in O(1) time whenever
the graph L ∩ H or the matrix Ex(L) changes. In fact, for all of O(1) edges e ∈ L and vertex pairs
/ v exists in H − e can be computed based only on Ex(L) and
u, v ∈ V (L), whether the path u
(L − e) ∩ H, when any of them changes, again in O(1) time (see the proof of Lemma 6.10). As the total
update time remains O(n log2 n log log n), the lemma follows.
Theorem 7.4. Let G be a planar digraph and let n = |V (G)|. The maximal 2-edge-connected subgraphs
of G can be maintained subject to edge deletions in O(n log2 n log log n) total time.
Proof. It is known that the maximal 2-edge-connected subgraphs can be found by repeatedly removing all
the strong bridges of G until none are left [17]. The maximal 2-edge-connected subgraphs of G are defined
as the strongly connected components of the obtained subgraph. Hence, we can combine Lemma 7.3
with our decremental strong connectivity algorithm to not only compute the maximal 2-edge-connected
subgraphs (by repeatedly detecting and deleting the arising strong bridges) but also to maintain them
subject to edge deletions.

7.2

Incremental Switch-On Transitive Closure

In this section we show how to solve the incremental transitive closure problem in planar graphs, under
the assumption that the embedding of the final planar graph is given upfront. We formulate this as a
dynamic graph problem, in which the input is a directed graph and each edge can be either on or off.
Initially all edges are off, and an update operation may turn a single edge on. Each query asks about
the existence of a directed path that connects two vertices and consists of edges that are on. The goal
of this section is to prove the following theorem.

19

Theorem 7.5. There exists an algorithm that can maintain a planar digraph under switching edges on
and√can answer reachability queries. Its total update time is O(n log2 n log log n) and the query time is
O( n log n log log n)
An easy corollary is as follows.
Theorem 7.6. There exists an algorithm that can maintain a planar digraph under contracting edges
and√can answer reachability queries. Its total update time is O(n log2 n log log n) and the query time is
O( n log n log log n)
Proof. Let G be the input graph. We build a graph Gsw which consists of G together with all reverse
edges of G. The graph Gsw is used as an input to the algorithm of Theorem 7.5. Initially, we switch on
all edges of G in Gsw .
Whenever an edge of G is contracted, we switch on its reverse edge in Gsw . This implies that at any
point, each vertex u of G corresponds to a strongly connected set of vertices of Gsw . We call this set
a group of u. Clearly, the groups partition V (Gsw ) and contracting all groups of Gsw yields G. Thus,
G
/ w, it suffices to check whether there exists a path
in order to check whether there exists a path u
u0

Gsw

/ w0 , where u0 and w0 are arbitrary vertices contained in the groups of u and w, respectively.

Let us now proceed with the proof of Theorem 7.5. We first recall some definitions from Section 6. By
G we denote the subgraph of G consisting of the edges that are switched on. Moreover, for each H of a
simple recursive decomposition T (G) we define In(H) to be a binary matrix with both rows and columns
H∩G
/ v.
indexed with the vertices of ∂H, such that In(H)u,v = 1 iff u, v ∈ ∂H and there exists a path u
2
Note that we show that these matrices can be maintained under switch-ons in O(n log n log log n) total
time. In addition, we can actually maintain the representation of these matrices used in the proof of
Theorem 5.1 (see Lemma 5.5).
To complete the description of our algorithm, we show how to use these matrices to answer queries
efficiently. For a subgraph H ∈ T (G) we define the dense reachability graph, denoted DRG(H), to
be a (possibly non-planar) graph on the vertices of ∂H, such that uv ∈ E(DRG(H)) iff there is a
H∩G
/ v. Thus, DRG(H) is fully described by In(H), that is DRG(H) = G(In(H)) (recall
path u
Definition 5.4).
G
/ w, we consider a graph
In order to answer a query asking about the existence of a path u
DRG(u,
w),
which
is
a
union
of
dense
reachability
graphs
(we
give
its
full
definition
later). This graph
√
has O( n) vertices in total, but can have as much as Θ(n) edges. Then, we show how to search for a
path in such a graph in time that is almost linear in the number of its vertices. This is somewhat similar
to the FR-Dijkstra algorithm for finding shortest paths in dense distance graphs [15], but due to lack of
edge weights our algorithm is slightly faster.
Let us now describe how DRG(u, w) is constructed. Let anc(H) be the set of ancestors of H in T (G),
including H, but excluding the root of T (G). Moreover, let sib(H) be the sibling of H in T (H). Recall
that G(In(H)) is the graph on ∂H, whose each edge corresponds to a path in H ∩ G.
We can now define DRG(u, w). Let Hu be any leaf node of T (G) that contains u and Hw be a leaf
node containing w. We have
[
DRG(u, w) := Hu ∪ Hw ∪
G(In(sib(H))).
H∈anc(Hu )∪anc(Hw )

Lemma 7.7. Let G be a planar digraph and T (G) be a simple recursive decomposition of G. Let
u, w ∈ V (G) and Hu and Hw be leaf nodes of T (G) that contain u and w. Then, either Hu = Hw and
every path from u to w is contained in Hu or every path from u to w contains a vertex x, such that
x ∈ ∂Hu0 ∩ ∂Hw0 , where Hu0 ∈ anc(Hu ) and Hw0 ∈ anc(Hw ).

Proof. Let H be the lowest common ancestor of Hu and Hw in T (G). There are three cases to consider.
If H is a leaf node, then Hu = Hw . Thus, every path from u to w is either fully contained in H or leaves
H in which case it contains a vertex of ∂H. If H is not a leaf node, but one of u, w (say, u) is contained
both in child1 (H) and child2 (H), then u ∈ ∂H, so the lemma holds trivially. Finally, if H is not a leaf
node, u and w are contained in distinct children of H. Thus, the path has to leave the child node of H
containing u (wlog. assume it to be child1 (H)), so it contains a vertex of ∂child1 (H). By the definition,
of vertex of ∂child1 (H) is also a vertex of ∂H or ∂child2 (H). Thus, the lemma follows.
20

Lemma 7.8. There exists a path u

G

/ w iff there exists a path u

DRG(u,w)

/ w.

Proof. By the construction, it is clear that each path in DRG(u, w) corresponds to a path that exists
G
/ w, then there also exists a path u DRG(u,w) / w.
in G. It remains to prove that if there is a path u
S
We show that DRG(u, w) contains paths from u to all vertices of H∈anc(Hu ) ∂H that are reachable
from
u in G. A symmetrical argument shows that DRG(u, w) contains paths to w from all vertices of
S
H∈anc(Hu ) ∂H thatScan reach w in G. By Lemma 7.7 this suffices to complete the proof.
Fix a vertex x ∈ H∈anc(Hu ) ∂H that is reachable from u in G. It suffices to show that x is reachable
S
from u in Hu ∪ H∈anc(Hu ) G(In(sib(H))), which is a subgraph of DRG(u, w). Consider H ∈ T (G).
Observe that if we modify G by replacing H with G(In(H)), then x is still reachable from u in the
obtained graph, as long as u and x are not removed,
that is, u, x 6∈ V (H) \ ∂H. To complete the
S
proof, it suffices to observe that the graph Hu ∪ H∈anc(Hu ) G(In(sib(H))) is indeed obtained from G
by performing such steps, as the graphs Hu ∪ {sib(H) | H ∈ anc(Hu )} are disjoint and each edge of G
is contained in exactly one of them.
In order to find a path in DRG(u, w) we use an algorithm based on breadth first search. We implement
it efficiently using ideas similar to those from the proof of Theorem 5.1. In the following pseudocode,
Out(a) denotes the set of tails of out-edges of a. The set Reachable is the set of vertices that have been
deemed reachable from u.
Algorithm 2 BFS algorithm
Input: A digraph G and u, w ∈ V (G).
1: function IsReachable(G, u, w)
2:
Q := empty queue
3:
Reachable := {u}
4:
Q.Enqueue(u)
5:
while Q is not empty do
6:
a := Q.Dequeue
7:
for x ∈ Out(a) \ Reachable do
8:
Reachable := Reachable ∪ {x}
9:
Q.Enqueue(x)
10:
return true iff w ∈ Reachable
Lemma 7.9. Algorithm 2 is correct.
Out(a) \ Reachable is linear in |V (G)|.

Its running time, excluding the time needed to compute

Proof. The correctness is clear, as this is an ordinary BFS-algorithm. The only difference is that the
for-loop only considers vertices unreachable from a. Clearly, the body of the for loop is executed once
per each vertex of G and each vertex of G is added to Q only once. Thus, the running time bound
follows.
Lemma 7.10. The graphs comprising DRG(u, w) can be decomposed into a collection
Au,wP
= {AS1 ,T1 , .√
. . , ASk ,Tk } of reachability matrices with the same properties as in Lemma 4.7, such
that i |Si | = O( n log n) and two constant-size arbitrary reachability matrices. All these matrices are
maintained by the algorithm that maintains the matrices In(H).
Proof. Recall that there are two types of graphs that comprise DRG(u, w). First, there are two O(1)
size graphs Hu and Hw whose reachability matrices In∗ (Hu ), In∗ (Hw ) are maintained explicitly by the
data structure of Section 6. All remaining graphs that comprise DRG(u, w) are of the form G(In(H)),
where H ∈ T (G). By Lemmas 4.7 and 6.8, each matrix In(H) can be decomposed into a family AH
of matrices with properties from the statement of Lemma 4.7 such that each row of In(H) is a row of
O(log |∂H|) matrices of AH . Thus,
√ ifi the level of H in T (G) is i, the total number of rows in matrices
n/c log n).
of AH is O(|∂H| log |∂H|) =
O(
S
We now define Au,w = H AH . Observe that for any level i of T (G), there are at most two graphs
G(In(H)) in T (G), such that H has level i. Thus, the total number of rows in the matrices of Au,w is
21

O

P

O(log n)
i=0

√


P∞
√
n/ci log n = O ( n log n) , since c > 1 implies i=0 1/ci = O(1). To finish the proof,

recall that the matrices of each AH (and thus Au,w ) are actually maintained explicitly by the data
structure of Section 6.
Lemma 7.11.
There exists an algorithm that determines whether there is a path u
√
runs in O( n log n log log n) time.

DRG(u,w)

/ w. It

Proof. We use the representation of DRG(u, w) from Lemma 7.10. Denote the matrices of this representation by In∗ (Hu ), In∗ (Hw ) and Au,w = {AS1 ,T1 , . . . , ASk ,Tk }.
For each AS,T ∈ Auw the algorithm maintains the set of candidates act(AS,T ) \ Reachable. as an van
Emde Boas tree. For the two matrices In∗ (Hu ), In∗ (Hw ), the set of candidates is maintained in an array.
In the remaining part of the proof we neglect the matrices In∗ (Hu ) and In∗ (Hw ) as they are constant-size
and thus each operation on them can be performed in O(1) time.
Whenever a vertex x is added to the set Reachable, it is removed from each set of candidates
containing it. In order to compute Out(a) \ Reachable, just as in the proof of Theorem 5.1, for each
AS,T ∈ Au,w such that a ∈ S we compute the intersection of the set {b ∈ T : AS,T
a,b = 1} and the set of
reachability candidates.
The running time of computing Out(a) \ Reachable and updating the set of reachability candidates
can be thus bounded as follows. For each AS,T ∈ Au,w , each element of T is added and removed at
most once from the set of reachability candidates. This takes
√ O(log log n) time, as the set is represented
with van Emde Boas tree. By Lemma 7.10, this takes O( n log n log log n) time, which dominates the
running time of Algorithm 2 (see Lemma 7.9).
It remains to prove Theorem 7.5.
Proof of Theorem 7.5. We first apply Lemma 6.1 to G to obtain the graph G0 such that |E(G0 )| = O(n)
and G0 has a simple recursive decomposition T (G0 ). The computation of T (G0 ), E0 , E1 , S, and p (as
defined in Lemma 6.1) takes O(n log n) time.
For each H ∈ T (G0 ) we maintain In(H) and its representation used in the proof of Theorem 5.1 (see
Lemma 5.5) under switching edges on. Similarly as in the proof of Lemma 6.3, all the edges of E0 ⊆ E 0
are switched on in G0 during the initialization, whereas the edges E 0 \ (E0 ∪ E1 ) are never switched on.
To handle the switch-on of edge e in G, we switch on the edge p(e) in G0 .
Denote by G and G0 the switched-on subgraphs of G and G0 , respectively. To decide whether there
exists a path u → v in G, by Corollary 6.2 we can equivalently check whether there exists a path u0 → v 0
in √
G0 , where u0 ∈ S(u) and v 0 ∈ S(v). Answering the reachability queries in G0 , by Lemma 7.11, takes
O( n log n log log n) time. The theorem follows.

8

The General Case of Non-Simple and Overlapping Holes

Let G = (V, E) be a planar digraph. This section is devoted to proving Lemma 6.1. To this end, we
transform our initial graph in a few steps. Each step produces an extended graph G0 = (V 0 , E 0 ) along
with disjoint subsets E0 , E1 ⊆ E 0 such that:
• there is a 1-to-1 mapping S between the vertices of V and the SCCs of (V 0 , E0 ).
• there is a 1-to-1 mapping p between E and E1 and for corresponding edges uv = e ∈ E and
u0 v 0 = p(e) ∈ E1 , the SCC of u0 (v 0 , resp.) in (V 0 , E0 ) corresponds to the vertex u (v resp.) of G,
i.e., u0 ∈ S(u) and v 0 ∈ S(v).
• The graph G0 is larger than G by a constant factor.
Roughly speaking, each step will alter the graph G obtained in the previous step by expanding its vertices
into strongly connected components of (V 0 , E0 ), mapping the edges E to E1 and adding some edges that
will belong to E 0 \ (E0 ∪ E1 ) and guarantee some structural property that we want. For brevity, we
sometimes only discuss the correspondences between the SCCs of G0 and vertices V and edges mapped
to the initial edge set E. We may skip the formal definitions of the mappings S and p.

22

It can be easily seen that after O(1) such steps the obtained graph is still larger than G only by a
constant factor. In each step we obtain a graph with more useful structural properties and our goal is
to eventually obtain a graph accompanied with a simple recursive decomposition.
Assume some first step transforms G = (V, E) into G0 = (V 0 , E 0 ) where E00 , E10 ⊆ E 0 and some second
step transforms G0 into G00 = (V 00 , E 00 ), where E000 , E100 ⊆ E 00 . We explain how the natural composition
of such steps works, i.e., how the mappings between G and G00 , along with the sets E0 , E1 , should look
like after applying these steps in sequence. Let p0 be the 1-to-1 mapping from E to E10 and let p00 be the
1-to-1 mapping from E 0 to E100 . We define E1 = p00 (p0 (E)) and p = p00 ◦ p0 . Moreover, E0 = E000 ∪ p00 (E00 ).
Observe that E0 , E1 ⊆ E 00 and E0 ∩ E1 = ∅. Note that (V 00 , E000 ) has no inter-SCC edges and there is
a mapping S 00 between V 0 and the SCCs of (V 00 , E000 ). Moreover, the insertion of edges p00 (E00 ) merges
some of the SCCs of (V 00 , E000 ) so that there are still no inter-SCC edges and there is still a natural 1-to-1
mapping between the SCCs of (V 00 , E0 ) and V .

8.1

Bounded-degree, Triangulated and Without Loops

The following two facts are folklore.
Fact 8.1. A triangulated plane embedded graph G is 3-connected.
Here, by triangulated we mean that each face of G has size exactly 3.
Fact 8.2. A plane embedded graph G has only simple faces if and only if G is biconnected.
The first step is to make G connected by adding a minimal number of edges: for the obtained
G0 = (V 0 , E 0 ), where V = V 0 and E ⊆ E 0 , we set E0 = ∅ and E1 = E. Clearly, G0 is also planar. In the
following, we assume G is connected.
We next fix some embedding of G in O(n) time [26]. Define an edge ring of v to be the sequence of
edges e1 , . . . , ek incident to v and ordered clockwise as implied by the embedding. Note that if some ei
is a loop, it appears in the edge ring of v twice.
We compute G0 based on G = (V, E) as follows. Let v be a vertex of G with an edge ring ev1 , . . . , evk .
Define C(v) to be a directed cycle v1 v2 . .S
. v3k , i.e., C(v) contains S
directed edges vi vi+1 for each i =
1, . . . , 3k, where v3k+1 = v1 . Define V 0 = v∈V V (C(v)) and E0 = v∈V E(C(v)). We also let S(v) =
V (C(v)) – clearly for each C(v), V [C(v)] is strongly connected.
For any uv = e ∈ E, suppose the tail of e appears as the i-th edge in the edge ring of u and its
head appears as the j-th edge in the edge ring of v. This is also well-defined in the case when e is a
loop. We include the edge u3i v3j in E1 . Clearly, the edge u3i v3j goes from a vertex in a SCC of (V 0 , E0 )
corresponding to u to a vertex in a SCC corresponding to v.
Note that H = (V 0 , E0 ∪ E1 ) is connected and let it naturally inherit the embedding from G. Observe
that each face of H either constitutes the interior of some cycle C(v) and has size at least 3, or is an
“expanded” version of one of the original faces of G and its bounding cycle has length at least 4. Hence,
we conclude that each face of H is of size at least 3.
Additionally, note that each vertex of H has degree at most 3. We finally obtain G0 from H by
triangulating each face f = w1 , . . . , wk , k > 3, of H by adding k − 3 edges inside it, so that no occurrence of a vertex of f gets added more than 2 edges. This can be achieved e.g., by adding edges
w1 w3 , w3 wk , wk w4 , w4 wk−1 , . . . and so on. These edges are included in E 0 \ (E0 ∪ E1 ). Observe that as
the vertices of H had degrees no more than 3, each vertex gains at most 6 additional edges in G0 . Thus,
G0 is triangulated and of constant degree. It is also clear that G0 has no loops.
Clearly, the described step can be implemented in O(n) time and produces a graph G0 with |V 0 | =
O(|E|) = O(|V |) and |E 0 | = O(|E|).

8.2

Admitting a Simple Recursive Decomposition

In this section we show how to transform a triangulated G of bounded degree into G0 such that we can
expose a simple recursive decomposition of G0 .
We first show how we build a (not necessarily simple) recursive decomposition of a planar digraph.
Lemma 8.3. Let G = (V, E) be an undirected triangulated plane graph and let n = |V |. A recursive
decomposition tree T (G) of G can be computed in O(n log n) time.
23

Proof. The algorithm essentially follows from [5, 33]. The decomposition tree that we use is in fact
identical to the one used by Klein et al. [33]. However, Klein et al. [33] use advanced data structures to
not build the decomposition tree explicitly, as their goal is to compute so-called r-divisions in linear time.
A trivial modification to their algorithm makes it possible to build the decomposition tree explicitly in
O(n log n) time (see Algorithm 1 in [33]).
The decomposition tree used by Borradaile et al. [5], on the other hand, essentially contains every
third level of the decomposition tree of [33] and is thus of degree > 2. However, their detailed analysis
of the sum of sizes of all subgraphs of T (G) and the sum of squares of boundary sizes, also easily applies
to the recursive decomposition of [33].
The algorithm of [33] also guarantees
that there exist constants c, d > 1 such that for any H ∈ T (G) on
√
we prove these bounds
the i-th level of T (G), |∂H| = O( n/ci ) and |V (H)| = O(n/di ). For completeness,
P
below. However, note that this properties alone do not necessarily imply H∈T (G) |∂H|2 = O(n log n),
as c might be smaller than 2.
The property |V (H)| = O(n/di ) is justified by the fact that the maximum
√ pnumber of vertices n(i)
of a level-i subgraph satisfies n(j) ≤ n(j − 1) and n(3j + 1) ≤ 32 n(3j) + 2 2 n(3j), for any valid j.
19
n(3j), and thus the desired property is satisfied with
Note that for n(3j) ≥ 100, we have n(3j + 1) ≤ 20

1/3
20
d = 19
.
The maximum number of boundary vertices b(i) of a level-i subgraph in [33] satisfies the following
inequalities for any valid j.
√ p
1. b(3j + 1) ≤ b(3j) + 2 2 n(3j).
√ p
2. b(3j + 2) ≤ 23 b(3j + 1) + 2 2 n(3j + 1).
√ p
3. b(3j + 3) ≤ b(3j + 2) + 2 2 n(3j + 2).
First note that b(3j + k) = O(b(3j + 2)), for k ∈ {0, 1}. Moreover,
observe that there exist
p
√ constants
q 0 > 0, q > 0, y > 1 such that b(3j + 2) ≤ 32 b(3(j − 1) + 2)√
+ q 0 n(3j) ≤ 32 b(3(j − 1) + 2) + q n/y j . Now
j
let c ∈ (1, min(3/2, y)).
√ Then we can prove b(3j + 2) ≤ p n/c , for some p > 0 as follows.
Assume b(2) ≤ p n for some p > 0 to be chosen later. For j > 0 we have b(3j + 2) ≤ 23 b(3(j − 1) +
√
√
√
√
√
√
j
2) + q n/y j ≤ 32 p n/cj−1 + q n/y j ≤ 2cp
n/cj + q n/y j ≤ ( 2cp
3
3 + q) n/c . It suffices to pick p such
2cp
that p ≥ 3 + q.
We refer to an important property of the algorithm of Klein et al. [33] that is used to build the
recursive decomposition T (G). Namely, in [33], the child subgraphs of H ∈ T (G) are obtained by
triangulating the holes of H and separating H using a simple cycle separator (see e.g., [39]). The following
Lemma precisely describes the relation between the parent and the children in the decomposition of [33].
Lemma 8.4. Let G be a plane triangulated graph. Let H be a non-leaf subgraph of T (G), where T (G)
is a decomposition produced by Lemma 8.3. There exists a Jordan curve CH (called a cycle separator)
going through distinct vertices v1 , . . . , vk ∈ V (H) (where vk+1 = v1 ) such that:
• The children of H are exactly the subgraphs of H contained respectively weakly-inside or weaklyoutside CH .
• For each i ∈ {1, . . . , k}, the part of CH going from vi to vi+1 either follows some (undirected) edge
vi vi+1 of H (we call it an edge-part) or otherwise is strictly contained inside some hole h of H
(we call it a hole-part) of size ≥ 4. Moreover the corners of h connected by the hole part vi vi+1
are not neighboring on h.
• For each hole h of H, there exists at most one hole-part of CH inside h.
• For i = 1, 2, all vertices of CH belong to ∂childi (H) and lie on a single hole h∗ of childi (H). All
holes h 6= h∗ of childi (H) are also holes of H and are located (weakly) on the same side of CH in
H as childi (H).
• The set E(child1 (H)) ∩ E(child2 (H)) contains exactly the edges corresponding to the edge-parts of
CH , whereas V (child1 (H)) ∩ V (child2 (H)) = CH .
24

The decomposition algorithms of [5, 33] can be modified to output all curves CH as a by-product of
computing T (G). The total running time of the algorithm remains O(n log n).
Let G be a plane embedded, triangulated digraph with bounded degree. Moreover, assume G does
not contain any loops. Let n = |V (G)| and let T (G) be a recursive decomposition build as in Lemma 8.3
(and possessing the properties summarized by Lemma 8.4). We now show how to use T (G) to build a
simple (see Definition 2.5) recursive decomposition T (G0 ) of a transformed graph G0 = (V 0 , E 0 ).
The decomposition T (G0 ) has the same shape as T (G) in the following sense.
• There is a 1-to-1 correspondence E : T (G) → T (G0 ) between the subgraphs of T (G) and the
subgraphs of T (G0 ).
• For the root subgraph G ∈ T (G), E(G) = G0 is the root of T (G0 ). Moreover, H ∈ T (G) has
children iff E(H) has children in T (G0 ) and E(childi (H)) = childi (E(H)) for i = 1, 2.
The graph G0 has the following additional properties which make the transformation G → G0 comply
with the requirements posed on a transformation step at the beginning of this section.
1. Each vertex v ∈ V 0 is mapped to a vertex orig(v) ∈ V (G).
2. Denote by E0 the subset of edges of G0 connecting vertices of u, v of G0 such that orig(u) = orig(v).
There is a 1-to-1 mapping S between the vertices G and the strongly connected components of
(V 0 , E0 ).
3. For any uv = e ∈ E there is an edge u0 v 0 = p(e) ∈ E 0 \ E0 such that orig(u0 ) = u and orig(v 0 ) = v
and p is injective.
8.2.1

Overview of the Construction

For each H ∈ T (G), H is conceptually extended, so that:
• Each vertex v ∈ V (H) is expanded to a directed cycle of sub-vertices of E(H). The cycle is further
split into smaller faces, corresponding to the expansions of v in the descendants of E(H) in T (G0 ).
• Each edge e ∈ E(H) is expanded to a undirected cycle (i.e., a cycle, but when ignoring the direction
of edges) in E(H). The cycle is further split into smaller faces, corresponding to the expansions of
e in the descendants of E(H).
• The subgraphs child1 (E(H)) and child2 (E(H)) are obtained from E(H) using the same (in a sense)
cycle separator as used to obtain child1 (H) and child2 (H) of H.
• There is a 1-to-1 correspondence between the faces of H and so-called original faces of E(H). In
particular, there is a 1-to-1 correspondence between the holes of H and E(H).
• By introducing vertex faces and edge faces, we separate the original faces (and thus the original
holes as well) of E(H), so that they do not share vertices.
• The size of each original hole of E(H) is larger by a constant factor than the size of the corresponding
hole of H.
• The leaf subgraphs of E(H) are of constant size as well.
Figure 5 shows how a subgraph H ∈ T (G) can be possibly expanded. Figure 6 shows how obtaining the
children of H ∈ T (G) with a cycle separator CH translates to obtaining the children of E(H).
The remaining part of this section is devoted to providing the technical details of the construction
sketched above.

25

8.2.2

Details of the Construction

Let H ∈ T (G). We first establish some structural requirements posed on the subgraphs of T (G0 ). Each
vertex v ∈ V (H) corresponds to a simple cycle QH (v) = v1 , . . . , vkv of vertices of V (E(H)) (ordered
clockwise). For each of these vi , we set orig(vi ) = v. Moreover, assuming vkv +1 = v1 , we have a directed
edge vi vi+1 ∈ E(E(H)) for each i ∈ [1, kv ]. These edges are called border vertex edges of v (with respect
to H).
Let el , . . . , ed be the edge ring of v in H. For i = 1, . . . , d, there is a contiguous subsequence QH
ei (v)
H
H
of vertices of QH (v). The fragments QH
e1 (v), . . . , Qed (v) are disjoint and put on Q (v) in the same order
as the edges e1 , . . . , ed lie in the edge-ring of v. However, there might be some other vertices in QH (v)
Sd
H
H
put between any two neighboring fragments QH
ei (v) and Qei+1 (v). We call
i=1 Qei (v) the edge vertices
H
H
of Q (v). An edge vertex that is either first or last in some Qei (v) is called a border edge vertex of v.
Sd
H
The remaining vertices X H (v) = QH (v) \ i=1 QH
ei (v) are called the extra vertices of Q (v). If d = 1,
H
H
then we require X (v) 6= ∅, so that the clockwise order of Qe1 (v) is well-defined. The extra vertices of
QH (v) can only be adjacent (in undirected sense) to other vertices of QH (v).
There may be some additional edges between the non-adjacent (but distinct) vertices of QH (v). All
such edges are always embedded inside the cycle QH (v) and do not cross. They partition the inside of
all these cycles into faces, which are collectively called the vertex faces of E(H). All edges connecting
pairs of vertices of QH (v) are called vertex edges of v (with respect to H).
H
Let uv = e ∈ E(H). Then, the fragments QH
e (u) = u1 , . . . , ul and Qe (v) = v1 , . . . , vl have equal
lengths and l ≥ 2. Recall that u 6= v, as we assume that G has no loops.
We have two edges u1 vl and ul v1 , which are called the border edge edges of e. Additionally, for each
i = 2, . . . , l − 1, there are two parallel edges ui vl−i+1 ∈ E(E(H)). These edges are called the internal
edge edges of e (with respect to H). The l − 1 rectangular faces ui vl−i+1 vl−i ui+1 (for i = 1, . . . , l − 1)
and l − 2 faces ui vl−i+1 of length 2 are collectively called the edge faces of e (with respect to H). Consult
Figure 5 for better understanding of how edge edges are constructed.
All the remaining faces of E(H) that are neither vertex faces nor edge faces are the original faces of
E(H). This name is justified by the fact that there is a 1-to-1 correspondence between such faces and
faces of H.
Lemma 8.5. No two original faces of E(H) share vertices.
Proof. Each original face f of E(H) consists of border vertex edges and border edge edges only. Note
that a border vertex edge on f has a vertex face on its other side. Similarly, a border edge edge on f
has an edge face on its other side. Thus, the faces adjacent to f are all vertex- or edge faces and hence
an original face f 0 6= f is not adjacent to f . We conclude that f and f 0 do not share vertices.
Lemma 8.6. All faces of E(H) are simple.
Proof. We prove that E(H) is biconnected, or equivalently, that any two distinct edges e, e0 ∈ E(E(H))
(ignoring their directions) lie on a simple cycle (in an undirected sense). By Fact 8.2, this will imply
that E(H) has only simple faces. Recall that biconnectivity is an equivalence relation on edges.
Clearly, if e, e0 are the edge edges of the same edge e∗ ∈ E(H), they lie on a simple cycle consisting
only of edge edges of e∗ .
The border vertex edges of some v all lie on a simple cycle by their definition. Moreover, each nonborder vertex edge of v is embedded inside this cycle and thus is biconnected with all the border vertex
edges. This establishes the biconnectivity of vertex edges of a single vertex v.
Note that the border edge edges of any uv = e ∈ E(H) lie on a simple cycle that includes both the
border vertex edges of u and v. Thus, all edge edges of e are biconnected with both the vertex edges of
u and vertex edges of v.
Observe that as H is connected, the above is enough to conclude that E(H) is biconnected.
It is clear that E0 = {u0 v 0 ∈ E 0 : orig(u) = orig(v)} contains only the vertex edges of E 0 and thus
there is a 1-to-1 correspondence between the vertices of V and the SCCs of (V 0 , E0 ). For e ∈ E, we
include in E1 any edge edge e0 of e and set p(e) = e0 .
We now have to guarantee that T (G0 ) has all properties of a recursive decomposition, and to this
end we pose additional requirements on E(H). Let D be a constant bounding the degree of G.
26

Figure 5: A directed embedded plane graph H (top) and an example extended graph E(H) (bottom).
The non-filled vertices are the extra vertices. Solid edges in the bottom picture are the border edge edges
of E(H), thick dashed edges are the border vertex edges, thin dashed edge is a non-border edge edge,
whereas the dotted edges are non-border vertex edges. The white faces are the original faces, gray faces
are the vertex faces, while the dotted faces are edge faces.

27

B.1 If v ∈ V (H) and v ∈
/ ∂H, then ∂E(H) ∩ QH (v) = ∅.
B.2 If v ∈ ∂E(H) and v is an edge vertex of QH (orig(v)), then v is a border edge vertex of QH (orig(v)).
B.3 For v ∈ V (H), the set X H (v) has size at most degG (v) − degH (v) + 1.
B.4 The holes of E(H) are exactly the original faces of E(H) corresponding to the holes of H.
B.5 If H is a leaf subgraph of T (G), then every edge vertex of E(H) is a border edge vertex and E(H)
has no non-border vertex edges.
Lemma 8.7. The above requirements imply that:
P
2
1.
H∈T (G) |∂E(H)| = O(n log n).

√
2. For any H ∈ T (G) of the i-th level of T (G), |∂E(H)| = O( n/ci ), where c = O(1).

3. Each leaf subgraph of ET (G) has O(1) edges.
Proof. Let H ∈ T (G). By B.2 and B.3, each v ∈ ∂H contributes at most 2 degH (v) edge vertices of v
and |X H (v)| ≤ degG (H) − degH (v) + 1 extra vertices of v to ∂E(H). Since degH (v) ≤ degG (v) ≤ D,
|∂E(H)| ≤ (2D + 1)|∂H| = O(|∂E(H)|). This implies both properties 1 and 2.
Let H be a leaf subgraph of T (G). Recall that H has O(1) edges. By B.3, B.5 and the structural
requirements posedP
on T (G0 ), for each v ∈ V (H), QH (v) has size at most 2 degH (v) + |X H (v)| = O(1)
and there are only v∈V (H) |QH (v)| = O(1) vertex edges. Thus, E(H) has at most O(1) edges.
Now we show how to actually build the subgraphs of T (G0 ) so that all the described requirements
are met and that T (G0 ) has all the needed properties of a recursive decomposition. This, combined with
Lemmas 8.5, 8.6 and 8.7 will finish the proof.
We will start with the root of T (G) and gradually move down the tree T (G), introducing new edge
vertices and edge edges of G0 once they are needed.
Each subgraph E(H) is created once. The boundary vertices of E(H) do not change after it is created,
but the graph E(H) itself might grow in a controlled way. We start by creating the root E(G) as a unique
graph such that:
• |QG
e (v)| = 2 for each e ∈ E(G) such that v is an endpoint of e.
• X G (v) = ∅ if degG (v) > 1 and |X G (v)| = 1 otherwise.
We set ∂E(G) = ∅. Clearly, these satisfies the requirements B.1-B.4 as ∂G = ∅ and there are no holes
in the root subgraph of T (G). Moreover, we can consider E(G) as a leaf of T (G0 ) at this point, as its
children have not been created yet. The property B.5 that characterized leaves is indeed satisfied for
E(G) at this point.
Each subsequent step of the construction will consist of taking a current leaf subgraph of T (G0 ) and
creating its children. We will proceed in such a way that the properties B.1-B.4 will remain satisfied for
all created subgraphs at all times. On the other hand, the property B.5 will cease to be satisfied when
subgraph stops to be a leaf of T (G0 ).
Now let H be a non-leaf subgraph of T (G) such that E(H) has been created, as opposed to its
children. Let CH = v1 , . . . , vk (where vk+1 = v1 ) be the cycle separator of Lemma 8.4.
For each edge part vi vi+1 of CH corresponding to an edge e ∈ E(H), we first create new edge vertices
H
H
bi , ai+1 by placing bi in QH
e (vi ) between the only two (see B.5) vertices of Qe (vi ) on the cycle Q (vi ).
H
H
H
Similarly, we put ai+1 in Qe (vi+1 ) between the only two vertices of Qe (vi+1 ) on the cycle Q (vi+1 ).
The newly created vertices are connected with a pair of new edge edges of e of the same direction as the
neighboring two edge edges of e in E(H). The insertion of the new vertices and edges is propagated to
all the ancestors of H. Note that the insertion of new edge vertices does not break properties B.1-B.5 of
E(H) and its ancestors (recall that H is non-leaf).
Let vi vi+1 be a hole part of CH inside the hole h of H. By Lemma 8.4, this hole part goes between
two distinct, non-neighboring corners ∠i , ∠i+1 of the hole h. Let j ∈ {i, i + 1}. Let ej1 , ej2 be the two,
possibly equal edges of ∠j . If ej1 6= ej2 , pick ej1 to be the edge following ej2 in the cycle bounding h (this
is well-defined, since h has at least 4 edges).
28

• If ej1 = ej2 , then degH (vj ) = 1 and for j = i (j = i + 1, resp.) we set bi (ai+1 , resp.) to be any
element of X H (vj ) – recall that X H (vj ) 6= ∅ in this case.
• Observe that if ej1 6= ej2 , then ej1 and ej2 cannot both correspond to edge parts of CH .

If ei1 lies on CH , then set bi to be the first edge vertex of QH
(v ). Otherwise, set bi to be the last
ei i
2

edge vertex of QH
(v ).
ei i
1

Similarly, If ei+1
lies on CH , then set ai+1 to be the first edge vertex of QH
(v ). Otherwise,
1
ei+1 i+1
set ai+1 to be the last edge vertex of QH
(v ).
ei+1 i+1

2

1

The vertices ai , bi are defined in such a way that ai 6= bi , ai , bi ∈ QH (vi ) and ai and bi are not next to
each other on QH (vi ). To see that, consider the parts vi−1 vi , vi vi+1 of CH . If both parts are edge parts,
then ai and bi are both edge vertices and are not border edge vertices. If both parts are hole parts, then
ai and bi are both last edge vertices of distinct edges incident to vi . If exactly one of vi−1 vi and vi vi+1
(say, vi−1 vi ) is an edge-part of CH , then ai is an edge vertex but not a border edge vertex of QH (vi ). If
degH (vi ) = 1, then bi ∈ X H (vi ) and otherwise bi is a border edge vertex of some other edge of QH (vi ).
For each i, let Pai bi (Pbi ai , resp.) be the clockwise path ai → bi (bi → ai , resp.) on QH (vi ). We
add edges eai bi = ai bi and ebi ai = bi ai inside the cycle QH (vi ) of E(H), so that the interiors of directed
cycles Pai bi ebi ai , Pbi ai eai bi do not intersect. Note the added edges do not violate the embedding (see B.5).
Similarly as before, these edges are added to all ancestors of E(H), consistently with the embedding.
Now, we define a Jordan curve C 0 going through vertices a1 , b1 , a2 , b2 , . . . , ak , bk : each part ai and bi
goes “between” the added edges eai bi and ebi ai (in other words, strictly inside the face bounded by these
two edges), whereas each part from bi to ai+1 is either inside an original hole of H or goes between a
pair of newly-added edge edges. We define childi (E(H)) (i = 1, 2) to be the part of E(H) weakly inside
(outside, resp.) C 0 iff childi (E(H)) is the subgraph of H weakly inside (outside, resp.) CH . Consult
Figure 6 for better understanding.
It is easy to see that childi (E(H)) satisfies all structural properties posed on E(childi (H)) at the
beginning of this section. Observe that ∂(childi (E(H))) contains the vertices {a1 , b1 , . . . , ak , bk } and
those vertices of ∂E(H) that lie strictly inside (outside resp.) C 0 . The definition of C 0 also guarantees,
that child1 (E(H)) and child2 (E(H)) have no edges in common.
Note that there are only two cases when for some vi ∈ CH and some j ∈ {1, 2}, degH (vi ) =
degchildj (H) (vi ). The first one is when vi−1 vi and vi vi+1 are both edge parts and additionally the
corresponding edges are neighboring in the edge ring of vi . But then both ai and bi are non-border edge
vertices of vi and thus the partition with C 0 does not introduce extra vertices of vi in either child1 (E(H))
or child2 (E(H)) that were not extra vertices in E(H). The second case is when (wlog.) vi−1 vi is an edge
part of CH corresponding to an edge of the cycle bounding h and vi vi+1 is a hole part going through the
corner ∠i of h incident to e. In this case degchild3−j (H) (vi ) is 1 and child3−j (E(H)) has one new extra
vertex of vi . However, no new extra vertices of vi are introduced in childj (E(H)).
Below we sketch how the properties B.1-B.5 are inductively satisfied for childi (E(H)) immediately
after its creation and that they still hold later in the process.
B.1 Recall that the boundary ∂childi (E(H)) is defined, by Lemma 8.4, as V (childi (E(H))) ∩ (C 0 ∪
∂E(H)) and thus is contained in C 0 ∪ ∂E(H). The property B.1 for childi (E(H)) follows from
the property B.1 for E(H) and the fact that for each i we have orig(ai ) = orig(bi ) = vi , i.e.,
orig(C 0 ) = CH and ∂childi (H) ⊆ ∂H ∪ CH .
B.2 When childi (E(H)) is created, it does not contain edge edges that are not border edge edges.
Also, when we create the descendants of childi (E(H)), only non-border edge edges are added to
childi (E(H)) and the boundary ∂childi (E(H)) is never extended.
B.3 It is sufficient to show it immediately after creating childj (E(H)), as no new extra vertices are
added to childj (E(H)) later on. The vertices ai , bi are defined in such a way that the size of
X childi (H) (vi ) can be greater than X H (vi ) by at most 1 and moreover this can only happen if
degchildj (H) (vi ) < degH (vi ). Thus |X childj (H) (vi )| − |X H (vi )| ≤ degH (vi ) − degchildj (H) (vi ). By
adding this inequality to |X H (vi )| ≤ degG (vi ) − degH (vi ) + 1, which follows from the property B.3
for H, we get the property B.3 for childi (H).

29

Figure 6: The top picture shows a graph H and a cycle separator CH (blue). The bottom picture shows
how the corresponding cycle separator C 0 splits E(H) into two parts. The orange part is child1 (E(H)),
while the rest – child2 (E(H)). Compare to Figure 5 to see which edges were added. The blue vertices are
the newly-introduced edge vertices. The white vertices represent extra vertices in either child1 (E(H)) or
child2 (E(H)).
30

B.4 Without loss of generality, assume that childi (E(H)) is the subgraph of E(H) weakly inside C 0 .
Note that each part of C 0 corresponding to the hole part of CH inside a hole h, lies inside the
original face of E(H) corresponding to h, by B.4 for E(H). On the other hand, for all holes h that
do not contain hole parts of CH , h is entirely on one side of CH , and thus the original face of E(H)
corresponding to h is on one side of C 0 . By combining this fact with property B.4 of E(H) and
Lemma 8.4, we get that the vertices ∂E(H) ∩ V (childi (E(H))) lie either on the original faces of
childi (E(H)) inside C 0 corresponding to the holes of both H and childi (H) inside CH , or on the
“external” original face of childi (E(H)), which corresponds to the “external” hole h∗ of childi (H).
The vertices ∂childi (E(H)) \ ∂E(H) are clearly contained in C 0 and thus lie on the “external”
original face of childi (E(H)) as well.
B.5 The new edges and vertices are introduced in E(H) in such a way that a child is given a separate pair
of edge edges for each edge of childi (H). Moreover, for each vi , childi (E(H)) inherits a contiguous
part of the cycle going through QH (vi ) and a single new edge ai bi or bi ai that closes the cycle. For
all vertices v ∈
/ CH , no non-border vertex edges of v are added to E(H) and thus no such edges
can exist in childi (E(H)).

References
[1] Amir Abboud and Søren Dahlgaard. Popular conjectures as a barrier for dynamic planar graph
algorithms. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016,
9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 477–486, 2016.
[2] 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, Philadelphia, PA, USA, October 18-21, 2014, pages 434–443, 2014.
[3] Ittai Abraham, Shiri Chechik, and Cyril Gavoille. Fully dynamic approximate distance oracles for
planar graphs via forbidden-set distance labels. In Proceedings of the 44th Symposium on Theory
of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 1199–1218,
2012.
[4] Surender Baswana, Manoj Gupta, and Sandeep Sen. Fully dynamic maximal matching in O(log n)
update time. SIAM J. Comput., 44(1):88–113, 2015.
[5] Glencora Borradaile, Piotr Sankowski, and Christian Wulff-Nilsen. Min st-cut oracle for planar
graphs with near-linear preprocessing time. ACM Trans. Algorithms, 11(3):16:1–16:29, 2015.
[6] Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, Veronika Loitzenbauer, and Nikos
Parotsidis. Faster algorithms for computing maximal 2-connected subgraphs in sparse directed
graphs. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1900–1918, 2017.
[7] Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, Jakub Łącki, and Nikos Parotsidis.
e √n ) total update
Decremental single-source reachability and strongly connected components in O(m
time. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11
October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 315–324, 2016.
[8] Camil Demetrescu and Giuseppe F. Italiano. A new approach to dynamic all pairs shortest paths.
J. ACM, 51(6):968–992, 2004.
[9] Camil Demetrescu and Giuseppe F. Italiano. Mantaining dynamic matrices for fully dynamic transitive closure. Algorithmica, 51(4):387–427, 2008.
[10] Reinhard Diestel.
Springer, 2012.

Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics.

[11] Krzysztof Diks and Piotr Sankowski. Dynamic plane transitive closure. In Algorithms - ESA 2007,
15th Annual European Symposium, Eilat, Israel, October 8-10, 2007, Proceedings, pages 594–604,
2007.
31

[12] David Eppstein, Zvi Galil, Giuseppe F. Italiano, and Thomas H. Spencer. Separator based sparsification: I. Planarity testing and minimum spanning trees. J. Comput. Syst. Sci., 52(1):3–27,
1996.
[13] David Eppstein, Giuseppe F. Italiano, Roberto Tamassia, Robert Endre Tarjan, Jeffery Westbrook,
and Moti Yung. Maintenance of a minimum spanning forest in a dynamic plane graph. J. Algorithms,
13(1):33–54, 1992.
[14] Shimon Even and Yossi Shiloach. An on-line edge-deletion problem. J. ACM, 28(1):1–4, 1981.
[15] 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.
[16] Pawel Gawrychowski and Adam Karczmarz. Improved bounds for shortest paths in dense distance
graphs. CoRR, abs/1602.07013, 2016.
[17] Loukas Georgiadis, Giuseppe F. Italiano, Luigi Laura, and Nikos Parotsidis. 2-edge connectivity in
directed graphs. ACM Trans. Algorithms, 13(1):9:1–9:24, 2016.
[18] Dora Giammarresi and Giuseppe F. Italiano. Decremental 2- and 3-connectivity on planar graphs.
Algorithmica, 16(3):263–287, 1996.
[19] Jens Gustedt. Efficient union-find for planar graphs and other sparse graph classes. Theor. Comput.
Sci., 203(1):123–141, 1998.
[20] Monika Henzinger, Sebastian Krinninger, and Veronika Loitzenbauer. Finding 2-edge and 2-vertex
strongly connected components in quadratic time. In Automata, Languages, and Programming 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I,
pages 713–724, 2015.
[21] Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. Sublinear-time decremental
algorithms for single-source reachability and shortest paths on directed graphs. In Symposium on
Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 674–683,
2014.
[22] Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. Improved algorithms for decremental single-source reachability on directed graphs. In Automata, Languages, and Programming 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I,
pages 725–736, 2015.
[23] Monika Rauch Henzinger and Mikkel Thorup. Sampling to provide or to bound: With applications
to fully dynamic graph algorithms. Random Struct. Algorithms, 11(4):369–379, 1997.
[24] Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. Poly-logarithmic deterministic fullydynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM,
48(4):723–760, 2001.
[25] Jacob Holm, Eva Rotenberg, and Christian Wulff-Nilsen. Faster fully-dynamic minimum spanning
forest. In Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, Sept. 14-16,
2015, Proceedings, pages 742–753, 2015.
[26] John E. Hopcroft and Robert Endre Tarjan. Efficient planarity testing. J. ACM, 21(4):549–568,
1974.
[27] Giuseppe F. Italiano, Yahav Nussbaum, Piotr Sankowski, and Christian Wulff-Nilsen. Improved
algorithms for min cut and max flow in undirected planar graphs. In Proceedings of the 43rd ACM
Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages
313–322, 2011.
[28] Ming-Yang Kao. Linear-processor NC algorithms for planar directed graphs I: strongly connected
components. SIAM J. Comput., 22(3):431–459, 1993.

32

[29] Haim Kaplan, Shay Mozes, Yahav Nussbaum, and Micha Sharir. Submatrix maximum queries in
Monge matrices and Monge partial matrices, and their applications. In Proceedings of the TwentyThird Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January
17-19, 2012, pages 338–355, 2012.
[30] Bruce M. Kapron, Valerie King, and Ben Mountjoy. Dynamic graph connectivity in polylogarithmic
worst case time. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete
Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 1131–1142, 2013.
[31] Valerie King. Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure
in digraphs. In 40th Annual Symposium on Foundations of Computer Science, FOCS ’99, 17-18
October, 1999, New York, NY, USA, pages 81–91, 1999.
[32] Philip N. Klein. Multiple-source shortest paths in planar graphs. In Proceedings of the Sixteenth
Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, BC, Canada,
January 23-25, 2005, pages 146–155, 2005.
[33] 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.
[34] Jakub Łącki. Improved deterministic algorithms for decremental reachability and strongly connected
components. ACM Trans. Algorithms, 9(3):27:1–27:15, 2013.
[35] Jakub Łącki and Yahav Nussbaum and Piotr Sankowski and Christian Wulff-Nilsen. Single source
- all sinks max flows in planar digraphs. In 53rd Annual IEEE Symposium on Foundations of
Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 599–608,
2012.
[36] Jakub Łącki and Jakub Oćwieja and Marcin Pilipczuk and Piotr Sankowski and Anna Zych. The
power of dynamic distance oracles: Efficient dynamic algorithms for the Steiner tree. In Proceedings
of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland,
OR, USA, June 14-17, 2015, pages 11–20, 2015.
[37] Jakub Łącki and Piotr Sankowski. Min-cuts and shortest cycles in planar graphs in O(n log log n)
time. In Algorithms - ESA 2011 - 19th Annual European Symposium, Saarbrücken, Germany,
September 5-9, 2011. Proceedings, pages 155–166, 2011.
[38] Jakub Łącki and Piotr Sankowski. Optimal decremental connectivity in planar graphs. In 32nd
International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4-7,
2015, Garching, Germany, pages 608–621, 2015.
[39] Gary L. Miller. Finding small simple cycle separators for 2-connected planar graphs. J. Comput.
Syst. Sci., 32(3):265–279, 1986.
[40] Shay Mozes and Christian Sommer. Exact distance oracles for planar graphs. In Proceedings of the
Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan,
January 17-19, 2012, pages 209–222, 2012.
[41] Liam Roditty and Uri Zwick. Improved dynamic reachability algorithms for directed graphs. SIAM
J. Comput., 37(5):1455–1471, 2008.
[42] Piotr Sankowski. Dynamic transitive closure via dynamic matrix inverse (extended abstract). In
45th Symposium on Foundations of Computer Science FOCS 2004, 17-19 October 2004, Rome,
Italy, Proceedings, pages 509–517, 2004.
[43] Shay Solomon. Fully dynamic maximal matching in constant update time. In IEEE 57th Annual
Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency,
New Brunswick, New Jersey, USA, pages 325–334, 2016.

33

[44] 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.
[45] Roberto Tamassia and Franco P. Preparata. Dynamic maintenance of planar digraphs, with applications. Algorithmica, 5(4):509–527, 1990.
[46] Roberto Tamassia and Ioannis G. Tollis. Dynamic reachability in planar digraphs with one source
and one sink. Theor. Comput. Sci., 119(2):331–343, 1993.
[47] Mikkel Thorup. Near-optimal fully-dynamic graph connectivity. In Proceedings of the Thirty-Second
Annual ACM Symposium on Theory of Computing, May 21-23, 2000, Portland, OR, USA, pages
343–350, 2000.
[48] Mikkel Thorup. Compact oracles for reachability and approximate distances in planar digraphs. J.
ACM, 51(6):993–1024, 2004.
[49] Mikkel Thorup. Worst-case update times for fully-dynamic all-pairs shortest paths. In Proceedings
of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24,
2005, pages 112–119, 2005.
[50] Peter van Emde Boas. Preserving order in a forest in less than logarithmic time and linear space.
Inf. Process. Lett., 6(3):80–82, 1977.
[51] 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, 2013.

34

