# On maximal $k$-edge-connected subgraphs of undirected graphs

Loukas Georgiadis University of Ioannina, Greece. E-mail<EMAIL_ADDRESS>Supported by the Hellenic Foundation for Research and Innovation (HFRI) under
the “First Call for HFRI Research Projects to support Faculty members and
Researchers and the procurement of high-cost research grant”, Project FANTA
(eFficient Algorithms for NeTwork Analysis), number HFRI-FM17-431. Giuseppe F.
Italiano Luiss University, Rome, Italy. Email<EMAIL_ADDRESS>Partially
supported by MUR, the Italian Ministry for University and Research, under PRIN
Project AHeAD (efficient Algorithms for HArnessing networked Data). Evangelos
Kosinas University of Ioannina, Greece. Email<EMAIL_ADDRESS>Supported
by the Hellenic Foundation for Research and Innovation (HFRI) under the 3rd
Call for HFRI PhD Fellowships (Fellowship Number: 6547). Debasish Pattanayak
Luiss University, Rome, Italy. Email<EMAIL_ADDRESS>Supported by MUR,
the Italian Ministry for University and Research, under PRIN Project AHeAD
(efficient Algorithms for HArnessing networked Data).

###### Abstract

We show how to find and efficiently maintain maximal $k$-edge-connected
subgraphs in undirected graphs. In particular, we provide the following
results. $(1)$ A general framework for maintaining the maximal $k$-edge-
connected subgraphs upon insertions of edges or vertices, by successively
partitioning the graph into its $k$-edge-connected components. This defines a
decomposition tree, which can be maintained by using algorithms for the
incremental maintenance of the $k$-edge-connected components as black boxes at
every level of the tree. $(2)$ As a concrete application of this framework, we
provide two algorithms for the incremental maintenance of the maximal
$3$-edge-connected subgraphs. These algorithms allow for vertex and edge
insertions, interspersed with queries asking whether two vertices belong to
the same maximal $3$-edge-connected subgraph, and there is a trade-off between
their time- and space-complexity. Specifically, the first algorithm has
$O(m\alpha(m,n)+n^{2}\log^{2}n)$ total running time and uses $O(n)$ space,
where $m$ is the number of edge insertions and queries, and $n$ is the total
number of vertices inserted starting from an empty graph. The second algorithm
performs the same operations in faster $O(m\alpha(m,n)+n^{2}\alpha(n,n))$ time
in total, using $O(n^{2})$ space. $(3)$ We provide efficient constructions of
(almost) sparse spanning subgraphs that have the same maximal $k$-edge-
connected subgraphs as the original graph. These are useful in speeding up
computations involving the maximal $k$-edge-connected subgraphs in dense
undirected graphs. $(4)$ We give two deterministic algorithms for computing
the maximal $k$-edge-connected subgraphs in undirected graphs, with running
times $O(m+k^{O(1)}n\sqrt{n}\,\mathrm{polylog}(n))$ and
$O(m+k^{O(k)}n\sqrt{n}\log{n})$, respectively. Hence, our first algorithm
improves the dependence on $k$ for deterministic algorithms, while our second
algorithm is faster than the randomized algorithm of Forster et al. (SODA
2020) for constant $k$. $(5)$ A fully dynamic algorithm for maintaining
information about the maximal $k$-edge-connected subgraphs for fixed $k$. Our
update bounds are ${O}(n\sqrt{n}\,\log n)$ worst-case time for $k>4$ and
${O}(n\sqrt{n}\,)$ worst-case time for $k\in\\{3,4\\}$. In both cases, we
achieve constant time for maximal $k$-edge-connected subgraph queries.

##  1 Introduction

A dynamic graph algorithm aims to maintain the solution of a given problem
after each update faster than recomputing it from scratch. An algorithm is
fully dynamic if it supports both insertions and deletions of edges, while it
is incremental (resp. decremental) if it only supports insertions (resp.
deletions) of edges.

Let $G=(V,E)$ be a connected undirected multigraph with $m$ edges and $n$
vertices. We let $V(G)$ and $E(G)$ denote the vertex set and the edge set of
$G$, respectively, i.e., $V(G)=V$ and $E(G)=E$. Let $S\subseteq V$ be any
subset of vertices of $G$. The _subgraph induced by $S$_, denoted by $G[S]$,
is defined as the graph having vertex set $S$ and edge set $\\{e\in
E\mid\mbox{both endpoints of }e\mbox{ lie in }S\\}$. Let $X,Y$ be two subsets
of $V$. $[X,Y]$ denotes the set of edges that have one endpoint in $X$ and the
other in $Y$. In other words, $[X,Y]=\\{(x,y)\in E\mid x\in X\mbox{ and }y\in
Y\\}$. Let $S\subset V$ be a non-empty (proper) subset of vertices of $G$, and
let $\bar{S}=V\setminus S\neq\emptyset$. If both $G[S]$ and $G[\bar{S}]$ are
connected, then $[S,\bar{S}]$ is called an _edge cut_ of $G$, i.e., a minimal
set of edges of $G$ such that its removal disconnects the graph. An edge cut
of cardinality $k$ is called a _$k$ -edge cut_ of $G$. As a special case,
$1$-edge cuts are also called _bridges_. $G$ is said to be _$k$ -edge-
connected_ if it contains no $k^{\prime}$-edge cuts, for $k^{\prime}<k$.

Two vertices of $G$ are said to be $k$-edge-connected if there are $k$ edge-
disjoint paths between them. The _edge-connectivity_ of a pair of vertices
$x,y\in V$, denoted as $\lambda_{G}(x,y)$ (or simply $\lambda(x,y)$, when $G$
is clear from context), is the maximum $k$ such that $x$ and $y$ are $k$-edge-
connected. The relation of “$k$-edge-connectivity” between pairs of vertices
of $G$ is an equivalence relation on $V(G)$ (see, e.g., [46]). The equivalence
classes induced by this relation are called the _$k$ -edge-connected
components_ of $G$. Thus, a $k$-edge-connected component of $G$ is a maximal
subset of vertices $C\subseteq V$ such that any pair of vertices in $C$ is
$k$-edge-connected. Notice that every $k$-edge-connected component lies
entirely within a $k^{\prime}$-edge-connected component, for every
$k^{\prime}<k$.

Now let $S\subseteq V$ be a subset of vertices in $G$. We say that the induced
subgraph $G[S]$ is a _maximal $k$-edge-connected subgraph_ of $G$ if (1)
$G[S]$ is $k$-edge-connected and (2) no proper superset of $S$ has this
property. Unlike 2-edge connectivity, for $k\geq 3$ the $k$-edge-connected
components of $G$ do not necessarily correspond to maximal $k$-edge-connected
subgraphs. Indeed, for $k\geq 3$, two vertices in the subgraph induced by a
$k$-edge-connected component may not be $k$-edge-connected in this subgraph,
as some of the $k$ edge-disjoint paths may go outside of the component; see
Figure 1. Also, Figure 2 shows a graph where almost all its vertices are
$3$-edge-connected but has only trivial maximal $3$-edge-connected subgraphs.
Notice that, if $S$ is a subset of $V$, then
$\lambda_{G[S]}(x,y)\leq\lambda_{G}(x,y)$ for any pair of vertices $x,y\in S$,
since every path in $G[S]$ is also a path in $G$. Thus, every maximal
$k$-edge-connected subgraph lies within the subgraph induced by a $k$-edge-
connected component.

Figure 1: A $2$-edge-connected graph $G$, its maximal $3$-edge-connected
subgraphs, and its $3$-edge-connected components. Note that while any two
vertices $x_{i}$ and $y_{j}$ are $3$-edge-connected, they do not belong to the
same maximal $3$-edge-connected subgraph.

Figure 2: A $2$-edge-connected graph $G$ with only trivial maximal $3$-edge-
connected subgraphs, despite that almost all vertices are $3$-edge-connected.

Determining or testing various notions of edge connectivity of undirected
graphs, as well as computing edge-connected components or subgraphs, is a
fundamental graph problem, and indeed $k$-edge connectivity has received much
attention in the literature. The problem of computing maximal $k$-edge-
connected subgraphs, however, appears to be harder than computing $k$-edge-
connected components, as not much progress has been made for the former
problem, despite its importance in the applications. As a matter of fact,
finding the maximal $k$-edge-connected subgraphs of a graph is of significant
interest in several areas, such as in the field of databases, social networks,
graph visualization etc. [3, 8, 9, 42, 50, 56, 58] (some of those papers refer
to the maximal $k$-edge-connected subgraphs as $k$-edge-connected components).

In more detail, it is known how to compute the $k$-edge-connected components
in linear time for $k\leq 4$ [24, 26, 29, 35, 44, 45, 51, 55]. On the other
hand, linear-time bounds for computing the maximal $k$-edge-connected
subgraphs are known only in the trivial case $k\leq 2$, simply because in
these cases the $k$-edge-connected components coincide with the maximal
$k$-edge-connected subgraphs. As mentioned in [10], the maximal $3$-edge-
connected subgraphs can be computed with a simple-minded algorithm in $O(mn)$
time in the worst case. Henzinger et al. [30] provided a deterministic
algorithm for computing the maximal $k$-edge-connected subgraphs, for constant
$k$, that runs in $O(n^{2}\log n)$ time. Chechik et al. [10] presented an
algorithm with running time $O(k^{O(k)}(m+n\log n)\sqrt{n}\,)$
($O(m\sqrt{n}\,)$ for $k=3$), which improves the bound of [30] for sparse
graphs. Forster et al. [20] gave a Las Vegas randomized algorithm for
computing the maximal $k$-edge-connected subgraphs in
$O(km\log^{2}{n}+k^{3}n\sqrt{n}\log{n})$ expected running time. Very recently,
Nalam and Saranurak [48] provided a randomized algorithm for computing the
maximal $k$-edge-connected subgraphs in _weighted_ undirected graphs in
$\widetilde{O}(m\cdot\min\\{m^{3/4},n^{4/5}\\})$ time. In the special case of
planar graphs, Holm et al. [34] showed how to compute the maximal $3$-edge-
connected subgraphs in $O(n)$ time.

###  1.1 Overview of our results

In this paper we present several new results on maximal $k$-edge-connected
subgraphs of undirected graphs. In particular, we provide the following
results.

  1. (1)

A general framework for maintaining the maximal $k$-edge-connected subgraphs
upon insertions of edges or vertices, by successively partitioning the graph
into its $k$-edge-connected components. This defines a decomposition tree,
which can be maintained by using algorithms for the incremental maintenance of
the $k$-edge-connected components as black boxes at every level of the tree.

  2. (2)

As an application of our new framework, we provide two algorithms for the
incremental maintenance of the maximal $3$-edge-connected subgraphs. These
algorithms allow for vertex and edge insertions, interspersed with queries
asking whether two vertices belong to the same maximal $3$-edge-connected
subgraph, and provide a trade-off between time- and space-complexity. The
first algorithm has $O(m\alpha(m,n)+n^{2}\log^{2}n)$ total running time and
uses asymptotically optimal $O(n)$ space, where $m$ is the number of edge
insertions and queries, and $n$ is the total number of vertices inserted
starting from an empty graph. The second algorithm improves the total running
time to $O(m\alpha(m,n)+n^{2}\alpha(n,n))$ (i.e., almost optimal for dense
graphs) at the expense of using $O(n^{2})$ space. We note that those are the
first incremental algorithms for this problem, and thus provide significant
improvements over recomputing the maximal $3$-edge-connected subgraphs after
every insertion.

  3. (3)

Using results from Benczúr and Karger [6], we provide efficient constructions
of (almost) sparse spanning subgraphs that have the same maximal $k$-edge-
connected subgraphs as the original graph. These are useful in speeding up
computations involving the maximal $k$-edge-connected subgraphs in dense
undirected graphs. In particular, we use those certificates to speed up the
computation of the maximal $k$-edge-connected subgraphs.

  4. (4)

Two deterministic algorithms for computing the maximal $k$-edge-connected
subgraphs in undirected graphs, with running times
$O(m+k^{O(1)}n\sqrt{n}\,\mathrm{polylog}(n))$ and
$O(m+k^{O(k)}n\sqrt{n}\log{n})$, respectively. Hence, our first algorithm
improves the dependence on $k$ for deterministic algorithms (which was
previously $k^{O(k)}$ [10]), while our second algorithm is faster than the
randomized algorithm of Forster et al. [20] for constant $k$.

  5. (5)

A fully dynamic algorithm for maintaining information about the maximal
$k$-edge-connected subgraphs for fixed $k$. Our update bounds are
${O}(n\sqrt{n}\,\log n)$ worst-case time for $k>4$ and ${O}(n\sqrt{n}\,)$
worst-case time for $k\in\\{3,4\\}$. In both cases we achieve constant time
for maximal $k$-edge-connected subgraph queries. Since no previous fully
dynamic bound was known for this problem, once again this improves on the
bounds obtainable by recomputing the maximal $k$-edge-connected subgraphs from
scratch after each update.

We believe that our main technical contribution is given by $(2)$. To achieve
this result, we provide a structural characterization of the maximal $3$-edge-
connected subgraphs of an undirected graph by introducing a decomposition tree
$\mathcal{T}$ into maximal $3$-edge-connected subgraphs, and show how to
maintain it efficiently under edge and vertex insertions. $\mathcal{T}$ is a
rooted tree whose root corresponds to the whole graph $G$ and is defined
recursively by computing the (subgraphs induced by the) $k$-edge-connected
components, for $k\in\\{1,2,3\\}$, of the graphs of the previous level. We
proceed recursively in this decomposition until we reach a graph that is
$3$-edge-connected, which is a maximal $3$-edge-connected subgraph of $G$ (and
a leaf of $\mathcal{T}$). Therefore, the nodes of $\mathcal{T}$ correspond to
subgraphs of $G$, and the parent relation is given by (vertex) set inclusion.
(See Section 3.3, and also Figure 4.)

Although maintaining the entire tree $\mathcal{T}$ may seem more challenging
than maintaining only the maximal $3$-edge-connected subgraphs, we show that
it is in fact easier to maintain the decomposition tree. This is because
$\mathcal{T}$ contains enough information to facilitate its efficient update
after new insertions to $G$, as its nodes corresponds to all successive
partitions of $G$ into $k$-edge-connected components, for $k\in\\{1,2,3\\}$.
In fact, if a new edge $e$ is inserted to $G$, then we only have to locate the
deepest subgraph $N$ on $\mathcal{T}$ that contains the endpoints of $e$, and
all changes to $\mathcal{T}$ due to this insertion apply to the subtree of
$N$. However, we do not explicitly maintain the correspondence between nodes
of $\mathcal{T}$ and subgraphs of $G$, as this would require as much as
$\Omega(mn)$ space (where $m$ is the number of edges and $n$ is the number of
vertices of $G$), and a much worse time to maintain $\mathcal{T}$ during a
sequence of insertions. Instead, we associate with the nodes of $\mathcal{T}$
some data structures that represent the interconnections between the $2$\- and
$3$-edge-connected components of the subgraphs that (abstractly) correspond to
the nodes of $\mathcal{T}$. To be more precise, we associate to every node of
$\mathcal{T}$ that corresponds to a connected component $C$ of its parent (a
representation of) the tree of the $2$-edge-connected components of $C$; and
to every node of $\mathcal{T}$ that corresponds to a $2$-edge-connected
component of its parent, we associate (a representation of) the cactus of its
$3$-edge-connected components. All this information reveals to be useful for
maintaining our tree decomposition with the help of previous incremental
approaches [27, 40, 41, 57]. We describe in detail, in Sections 5 and 6, how
we can augment the previous incremental approaches with enough information to
suit our purposes.

Notice that in the bounds provided in $(2)$, there is a trade-off between
space- and time-complexity. The second algorithm is more time-efficient (at
least asymptotically), due to the following two reasons. First, we find a way
to use the more sophisticated data structures of La Poutré [40], in order to
efficiently maintain the $2$\- and $3$-edge-connected components of the graphs
in the various levels of $\mathcal{T}$. Secondly, we use an alternative and
more intriguing method for answering nearest common ancestor and level
ancestor queries, that are needed in the algorithm for maintaining
$\mathcal{T}$. This method relies on the structure of those queries (i.e.,
they are not completely arbitrary but they depend on modifications already
made on $\mathcal{T}$). However, in order to facilitate the efficient
answering of those queries, we pay an extra $O(n^{2})$ in space. In any case,
the $n^{2}$ factor in the time-bound of both algorithms is an inherent
bottleneck of the basic procedure that we use, for any sequence of insertions,
and a lower bound on the worst-case time for a single insertion (see Figure 3
and Algorithm 1).

Both our algorithms can efficiently answer queries concerning the maximal
$3$-edge-connected subgraphs in asymptotically optimal time, plus the time to
perform one or two calls to a $\mathit{find}$ operation in an underlying
disjoint set union (DSU) data structure [52] that maintains the vertex sets of
the maximal $3$-edge-connected subgraphs. (For the details on this DSU data
structure, see Section 4.) For instance, given two query vertices $x$ and $y$,
we can report whether $x$ and $y$ belong to the same maximal $3$-edge-
connected subgraph using two calls to a $\mathit{find}$ operation, or given a
query vertex $x$ we can report the maximal $3$-edge-connected subgraph that
contains $x$ in time proportional to its size plus a call to a $\mathit{find}$
operation. (See Section 10.)

We note that these algorithms can be seen as applications of a more general
framework for maintaining the maximal $k$-edge-connected subgraphs, by relying
on algorithms that maintain the $k$-edge-connected components (result $(1)$).
We think that it is possible that one can develop a similar framework for
maintaining the maximal $k$-vertex-connected subgraphs, by relying on
efficient algorithms for maintaining the $k$-vertex-connected components. (In
particular, for the case $k=3$, one may rely on the algorithms of [5, 39] for
maintaining the $3$-vertex-connected components.)

For $(3)$, we show that it is sufficient to compute (a superset of) all the
edges whose endpoints lie in different maximal $k$-edge-connected subgraphs.
Benczúr and Karger [6] provide efficient algorithms that achieve this. From
those algorithms we get two different constructions for spanning subgraphs
that have the same maximal $k$-edge-connected subgraphs as the original graph,
and there is a trade-off between the time complexity and the size of the
output subgraph. Following the terminology of [1], we call such a subgraph a
$k$-certificate. Then, we have a linear-time algorithm for computing a
$k$-certificate with $O(kn\log{n})$ edges, and an $O(m\log^{2}{n})$-time
algorithm for computing a $k$-certificate with $O(kn)$ edges (where $m$ and
$n$ denote the number of edges and vertices of the graph, respectively). A key
component in those algorithms is the certificates for $k$-edge connectivity of
Nagamochi and Ibaraki [47]. For the details, see Section 7. We believe that it
is an interesting question whether a $k$-certificate of $O(kn)$ size can be
computed in linear time. This would be trivial if we had a linear-time
algorithm for computing the maximal $k$-edge-connected subgraphs of a graph,
but it is still an open problem whether this can be done for $k\geq 3$. Thus,
we have to perform the construction of the certificates without explicitly
computing the maximal $k$-edge-connected subgraphs, and this seems to be a
challenging task.

For $(4)$ we provide two different deterministic algorithms by using two
essentially different approaches. The idea in the first approach is to
repeatedly find and remove all $k^{\prime}$-edge cuts, for $k^{\prime}<k$. For
this purpose we can rely on the fully dynamic min-cut algorithm of Thorup
(Theorem $26$ in [54]). Thus, we use this algorithm in order to successively
find and remove all $k^{\prime}$-edge cuts, for $k^{\prime}<k$, until we are
left with the maximal $k$-edge-connected subgraphs. This is how we get a
deterministic algorithm with $O(m+k^{O(1)}n\sqrt{n}\mathrm{polylog}(n))$
worst-case time for computing the maximal $k$-edge-connected subgraphs of a
graph with $m$ edges and $n$ vertices. This algorithm is described in Section
8. Alternatively, we may use our result $(3)$, in order to get in linear time
a subgraph with $O(kn\log n)$ edges that has the same maximal $k$-edge-
connected subgraphs as the original graph, and then we may apply the algorithm
by Chechik et al. [10], that runs in $O(k^{O(k)}(m+n\log n)\sqrt{n}\,)$ time.
Thus we get an $O(m+k^{O(k)}n\sqrt{n}\log n)$-time algorithm for computing the
maximal $k$-edge-connected subgraphs. We note that the previously best known
deterministic algorithm for computing the maximal $k$-edge-connected subgraphs
in dense graphs, for constant $k$, is given by Henzinger et al. [30], and runs
in $O(n^{2}\log n)$ time. For sparse graphs, the best time-bound is provided
by Chechik et al. [10], which is $O((m+n\log n)\sqrt{n}\,)$ for $k>4$, and
$O(m\sqrt{n}\,)$ for $k\in\\{3,4\\}$111The improved time-bound for
$k\in\\{3,4\\}$ is due to the existence of linear-time algorithms for
computing $2$\- and $3$-edge cuts. (See, e.g. [29, 44, 55].) For $k>4$ we rely
on Gabow’s algorithm [23], which runs in almost linear time.. Hence, our first
algorithm improves the dependence on $k$ for deterministic algorithms from
exponential to polynomial, while our second algorithm is faster than the
randomized algorithm of Forster et al. [20] for constant $k$.

For $(5)$ we rely on the sparsification framework of Eppstein et al. [19]. We
show that we can apply the certificates that we provide in Section 7, and we
use the algorithm of Chechik et al. [10] for the updates. For the details, see
Section 9.

###  1.2 More related work

Dynamic graph algorithms have been extensively studied for several decades,
and many important results have been achieved for fundamental problems such as
dynamic connectivity [21, 28, 32, 43], minimum spanning trees [19, 22, 49],
minimum cut [38, 40, 54], shortest paths [2, 7, 12, 53], and transitive
closure [31]. Regarding dynamic algorithms for maintaining $k$-connectivity
information (for small values of $k$) has also received a lot of attention
[15, 16, 18, 19, 25, 33, 36, 37, 40, 41, 57]. This previous work, however,
involves maintaining a graph under edge insertions and/or deletions, so that
we can efficiently answer queries of whether two vertices are $k$-edge- or
$k$-vertex-connected (i.e., belong to the same $k$-edge- or $k$-vertex-
connected component). Very recently, Aamand et al. [1] provided a Monte Carlo
randomized algorithm for the decremental maintenance of the maximal $c$-edge-
connected subgraphs, that has $O(m+n^{3/2+o(1)})$ total update time and $O(1)$
query time, for $c=O(n^{o(1)})$. To the best of our knowledge, no previous
non-trivial bounds were known for the dynamic maintenance of maximal $3$-edge-
connected subgraphs with a deterministic algorithm.

###  1.3 Organization

The rest of the paper is organized as follows. First, we provide some
preliminaries in Section 2. We describe our decomposition tree of the maximal
$3$-edge-connected subgraphs in Section 3.3. This can be seen as an
application of a general framework for maintaining the maximal $k$-edge-
connected subgraphs by using algorithms for maintaining the $k$-edge-connected
components, which is described in Sections 3.1 and 3.2. The details on
maintaining the decomposition tree of the maximal $3$-edge-connected subgraphs
under insertions of new edges and vertices is given in Section 4. In Sections
5 and 6 we present efficient implementations for the data structures that are
associated with the nodes of the decomposition tree, in order to efficiently
update it. In Section 7 we present a linear-time construction of sparse
certificates for maximal $k$-edge-connected subgraphs. From this we derive a
deterministic $O(m+k^{O(k)}n\sqrt{n}\log n)$-time algorithm for computing the
maximal $k$-edge-connected subgraphs. In Section 8 we provide an
$O(m+k^{O(1)}n\sqrt{n}\mathrm{polylog}(n))$ deterministic algorithm for
computing the maximal $k$-edge-connected subgraphs, using Thorup’s fully
dynamic mincut algorithm. Section 9 presents our fully dynamic algorithm for
maximal $k$-edge-connected subgraphs. We conclude in Section 10 with
suggestions for further applications of our decomposition tree.

##  2 Preliminaries

In the sequel, we assume that the reader is familiar with standard graph
terminologies, for example, as presented in [11, 13, 46]. For the sake of
completeness, we provide some definitions and state some results that will be
used throughout concerning the structure of the $2$\- and $3$-edge-connected
components in undirected graphs. Consider the quotient graph $Q^{k}$ of $G$
that is formed by shrinking every $k$-edge-connected component into a single
vertex, maintaining all inter-connection edges and discarding self-loops. Then
the quotient map $\nu:V(G)\rightarrow V(Q^{k})$ induces a natural
correspondence between the edges of $Q^{k}$ and some edges of $G$: that is,
for every edge $(u,v)$ of $Q^{k}$, there is an edge $(x,y)\in E(G)$ such that
$\nu(x)=u$ and $\nu(y)=v$. Now, for $k=2$, we have that $Q^{2}$ is a tree $T$.
The nodes of $T$ correspond to the $2$-edge-connected components of $G$, and
the edges of $T$ correspond to the bridges of $G$. Now let $C$ be a $2$-edge-
connected component of $G$. Then we have that $G[C]$ is $2$-edge-connected,
and every $k$-edge-connected component of $G$ that lies in $C$, for $k\geq 2$,
is also a $k$-edge-connected component of $G[C]$. For $k=3$, the quotient
graph $Q^{3}$ of $G[C]$ is a _cactus_ $S$ (that is, a connected graph in which
every edge belongs to a unique cycle) [17, 27, 41]. The nodes of $S$
correspond to the $3$-edge-connected components of $G[C]$ and the $2$-edge
cuts of $Q^{3}$ correspond to the $2$-edge cuts of $G[C]$. (We note that these
properties generalize to the _cactus of the minimum cuts_ of an undirected
graph [14].)

Now let us consider how the insertion of a new edge $(x,y)$ to $G$ affects its
$k$-edge-connected components, for $k\leq 3$. (In general, observe that the
edge-connectivity for any pair of vertices increases at most by one.) We
distinguish four different cases, depending on whether
$\lambda(x,y)\in\\{0,1,2\\}$ or $\lambda(x,y)\geq 3$, prior to the insertion
of $(x,y)$.

  1. (1)

If $\lambda(x,y)=0$, then $x$ and $y$ belong to two different connected
components $C_{1}$ and $C_{2}$, respectively. Thus the only change that occurs
is that $\lambda(u,v)=1$, for any two vertices $u\in C_{1}$ and $v\in C_{2}$.

  2. (2)

If $\lambda(x,y)=1$, then $x$ and $y$ belong to the same connected component
$C$, and lie in two different $2$-edge-connected components $X$ and $Y$,
respectively. Let $T$ be the tree of the $2$-edge-connected components of
$G[C]$, and let $P=X_{1},\dots,X_{k}$ be the simple path on $T$ with endpoints
$X$ and $Y$ (i.e., we have $X_{1}=X$ and $X_{k}=Y$). Then, after inserting
$(x,y)$, we have $\lambda(u,v)\geq 2$, for any pair of vertices $u,v\in
X_{1}\cup\dots\cup X_{k}$, and $\lambda(u,v)$ stays the same for any other
pair of vertices. In particular, this implies that $X_{1}\cup\dots\cup X_{k}$
is a new $2$-edge-connected component. Now, for every edge $(X_{i},X_{i+1})$,
$i\in\\{1,\dots,k-1\\}$, of $T$, let $(x_{i},y_{i})$ be the edge of $G$ that
corresponds to $(X_{i},X_{i+1})$, and let $(x,y)=(y_{0},x_{k})$ (this is for
notational convenience). Then, for every $i\in\\{1,\dots,k\\}$, we have
$y_{i-1},x_{i}\in X_{i}$, and the remaining changes in the $k$-edge-connected
components of $G$, after inserting $(x,y)$, are given by supposing that we
introduce a virtual edge $(y_{i-1},x_{i})$ to $G$; thus they are described
sufficiently in the following two cases.

  3. (3)

If $\lambda(x,y)=2$, then $x$ and $y$ belong to the same $2$-edge-connected
component $C$, and lie in two different $3$-edge-connected components of
$G[C]$. Let $S$ be the cactus of the $3$-edge-connected components of $G[C]$.
Then, after inserting $(x,y)$, we have that at least $X$ and $Y$ are now
united into a larger $3$-edge-connected component (together with some other
nodes of $S$). To describe precisely the nodes of $S$ that get united into a
new $3$-edge-connected component, we introduce the concept of the _cycle-path_
on $S$ connecting $X$ and $Y$. Let $Z_{1},\dots,Z_{k}$ be a simple path on $S$
with $Z_{1}=X$ and $Z_{k}=Y$. Then the cycle-path $Q$ connecting $X$ and $Y$
on $S$ is the set of nodes consisting of $X$, $Y$, and all $Z_{i}$,
$i\in\\{2,\dots,k-1\\}$, such that the edges $(Z_{i-1},Z_{i}),(Z_{i},Z_{i+1})$
belong to different cycles of $S$. (Notice that this definition is independent
of the choice of the simple path $Z_{1},\dots,Z_{k}$.) Then, after inserting
$(x,y)$, all the nodes of $Q$ are merged into a new maximal $3$-edge-connected
component. The edge-connectivity between any pair of vertices $u$ and $v$, not
both of which lie in nodes of $Q$, stays the same. Observe that the new cactus
of the $3$-edge-connected components of $G[C]$ is given by $S$ where we have
“squeezed” every cycle $c$ that contains two consecutive nodes $Z$ and $W$ of
$Q$, by merging $Z$ and $W$ into a new node $U$. (If $Z$ and $W$ are not
connected with an edge on $S$, then the squeezing of $c$ at $Z$ and $W$
produces two new cycles that meet at $U$.)

  4. (4)

If $\lambda(x,y)\geq 3$, then all the $k$-edge-connected components of $G$,
for $k\leq 3$, stay the same [15].

##  3 The decomposition tree of the maximal $k$-edge-connected subgraphs

In this section we provide a general framework for maintaining the maximal
$k$-edge-connected subgraphs of an undirected graph upon insertions of edges
or vertices. This framework relies on a structural characterization of the
maximal $k$-edge-connected subgraphs that is derived from the repeated
decomposition of the graph into its $k$-edge-connected components. Thus we get
a decomposition tree, which can be maintained by using any algorithm for the
incremental maintenance of the $k$-edge-connected components (that satisfies
some properties) as a black box. We provide a concrete application of this
framework: two algorithms for maintaining the maximal $3$-edge-connected
subgraphs. These algorithms provide a trade-off between time- and space-
bounds, because they rely on different algorithms for maintaining the
$3$-edge-connected components, and they utilize the structure of the
decomposition tree in different ways.

###  3.1 A general framework for maintaining the $k$-edge-connected subgraphs

In what follows we let “$k$-ecc” mean “$k$-edge-connected component”. We will
not distinguish between the vertex set of a $k$-ecc and the subgraph induced
by it. Let $G$ be an undirected multigraph with $m$ edges and $n$ vertices. We
consider the decomposition tree $\mathcal{T}$ of the maximal $k$-edge-
connected subgraphs of $G$, which is a rooted tree whose nodes correspond to
subgraphs of $G$. It is defined recursively as follows. $(1)$ The root of
$\mathcal{T}$ corresponds to $G$. $(2)$ Every node of $\mathcal{T}$ that
corresponds to a $k$-edge-connected subgraph of $G$ is a leaf. $(3)$ The
children of every node $N$ of $\mathcal{T}$ that is not a leaf correspond to
the $k$-eccs of the subgraph of $G$ corresponding to $N$. This completes the
recursive definition of $\mathcal{T}$. Observe that the size of $\mathcal{T}$
is $O(n)$, because the leaves of $\mathcal{T}$ correspond precisely to the
maximal $k$-edge-connected subgraphs of $G$ (which are at most $n$), and every
node of $\mathcal{T}$ is either a leaf or it has at least two children.

We observe that $\mathcal{T}$ has the following useful property.

######  Property 3.1.

Let $G$ be an undirected graph, and consider the quotient graph $Q$ that is
formed by shrinking a maximal $k$-edge-connected subgraph of $G$ into a single
vertex. Then $Q$ has the same decomposition tree into maximal $k$-edge-
connected subgraphs as $G$.

We use this decomposition tree because we want to maintain the maximal
$k$-edge-connected subgraphs of $G$ while new edges or vertices are inserted
to it. The definition using successive partitions into $k$-edge-connected
components is convenient, because every maximal $k$-edge-connected subgraph
lies entirely within a $k$-edge-connected component, and we can utilize
algorithms for the incremental maintenance of the $k$-edge-connected
components (that satisfy some properties) in order to maintain the
decomposition tree under new insertions.

Now let us describe the changes that take place in $\mathcal{T}$ after a new
edge is inserted to $G$. Suppose a new edge $e=(x,y)$ is inserted to $G$. Let
$X$ and $Y$ be the maximal $k$-edge-connected subgraphs of $G$ that contain
$x$ and $y$, respectively. If $X=Y$, there is nothing to do. Otherwise, we
find the nearest common ancestor $N$ of $X$ and $Y$ on $\mathcal{T}$, and
perform the insertion of $e$ to $N$. Observe that $N$ is the deepest node of
$\mathcal{T}$ that contains both $x$ and $y$. It is sufficient to perform the
insertion of $e$ to $N$, because $N$ is separated from its siblings by a
$k^{\prime}$-edge cut, for some $k^{\prime}<k$, and this does not change even
if we insert $e$ to $N$. Thus, all changes in $\mathcal{T}$ after the
insertion of $e$ to $G$ take place in the subtree of $N$. If $x$ and $y$ do
not become $k$-edge-connected in $N$, then no change takes place in
$\mathcal{T}$. Otherwise, some $k$-eccs of $N$ get merged into a larger
$k$-ecc. If all vertices of $N$ become $k$-edge-connected, then $N$ becomes a
leaf node. Otherwise, we have to find its children that correspond to the
$k$-eccs of $N$ that get merged, and substitute them with a single child that
corresponds to the bigger $k$-ecc that is formed. Then we have to push down to
the new child all the edges that have their endpoints in different $k$-eccs
that got merged. In effect, we re-insert those edges to the child of $N$ that
represents the new $k$-ecc that is formed. This completes the recursive
description of the changes that take place in $\mathcal{T}$ after inserting a
new edge to $G$.

In order to efficiently maintain the decomposition tree, we will have to
attach more information to it. We discuss this in the following section, where
we use as a black box any algorithm that maintains the $k$-edge-connected
components (and satisfies some conditions). In any case, it is interesting to
note - and it is essential in proving our time bounds - that the number of
edge insertions that can affect the decomposition tree, in any sequence of
edges insertions, is $O(n)$. This is formally stated and proved in Theorem
3.3.

######  Lemma 3.2.

[1] Let $G$ be a graph with $n$ vertices and $m$ edges, such that every
maximal $k$-edge-connected subgraph of $G$ is trivial. Then $m\leq(k-1)(n-1)$.

######  Theorem 3.3.

Let $k\geq 3$, and let $G_{0}=(V,E_{0})$ be an empty graph with $n$ vertices
and no edges ($E_{0}=\emptyset$). Let $e_{1},\dots,e_{m}$ be a sequence of
edges joining vertices of $V$, and define $E_{i}=\\{e_{1},\dots,e_{i}\\}$ and
$G_{i}=(V,E_{i})$, for $i=1,\dots,m$. Then, $|\\{i\in\\{1,\dots,m\\}\mid
e_{i}\mbox{ joins two different maximal }k\mbox{-edge-connected subgraphs of
}G_{i-1}\\}|\leq k(n-1)$.

###### Proof.

We proceed by induction on the number $n$ of vertices. For $n=1$, the theorem
trivially holds, as there are no possible edge insertions. Assume that the
theorem holds for every graph with at most $n$ vertices, for some $n\geq 1$.
Given an empty graph with $n+1$ vertices, we will show that at most $kn$ edges
can affect the decomposition tree during any sequence $e_{1},\dots,e_{m}$ of
edge insertions.

Let ${\ell}$, $0\leq\ell\leq m-1$, be the lowest index such that
$G_{\ell+1}=(V,E_{\ell+1})$ contains a non-trivial maximal $k$-edge-connected
subgraph (i.e., $G_{i}=(V,E_{i})$, $0\leq i\leq\ell$ contain only trivial
maximal $k$-edge-connected subgraphs). If no such index $\ell$ exists, then
the final graph $G_{m}$ has only trivial maximal $k$-edge-connected subgraphs
and the theorem holds by Lemma 3.2. Otherwise, let $S$ be the non-trivial
maximal $k$-edge-connected subgraph that appears in $G_{\ell+1}$ after the
edge $e_{\ell+1}$ has been inserted to $G_{\ell}$, and let $S$ contain $d$
vertices ($d\geq 2$) and $t$ edges. Note that $e_{\ell+1}$ must necessarily be
in $S$. Let $S^{\prime}=S\setminus e_{\ell+1}$: then $S^{\prime}$ has $d\geq
2$ vertices and $t-1$ edges, and contains only trivial maximal $k$-edge-
connected subgraphs. By Lemma 3.2 applied to $S^{\prime}$, we have
$t-1\leq(k-1)(d-1)$, and therefore $t\leq(k-1)(d-1)+1$.

Now let us consider the quotient graph of $G_{\ell+1}/S$ that is formed by
contracting $S$ into one single vertex. This quotient graph has $\ell+1-t$
edges and $(n+1)-d+1=n-d+2\leq n$ vertices (since $d\geq 2$). Since we are
contracting a maximal $k$-edge.connected subgraph, the quotient graph has
exactly the same decomposition tree as $G_{\ell+1}$. By induction, there are
at most $k((n-d+2)-1)-(\ell+1-t)=kn-kd+k-\ell-1+t$ new edges that can be added
to the quotient graph and affect its decomposition tree. This number is at
most $kn-\ell-d+1$ (since $t$ is at most $kd-k-d+2$). Since we have already
added $\ell+1$ edges to the initial graph, we have that, in total, at most
$kn-d+2$ edges can affect the decomposition tree. The fact that $d\geq 2$
yields the desired result. ∎

###  3.2 Maintaining the decomposition tree

In order to be able to update $\mathcal{T}$ after a new insertion to the
graph, we need a $k$-edge-connected components algorithm that satisfies the
following properties. The algorithm works on an incremental graph $G$ and
maintains a unique label for every $k$-ecc of $G$. Furthermore, it supports
the following two operations.

  1. 1.

When a new edge is inserted to $G$, return the labels of the $k$-eccs of $G$
that get merged due to this insertion, the label of the new $k$-ecc that is
formed, and the set of the interconnection edges between those $k$-eccs that
get merged.

  2. 2.

Given a collection of vertex-disjoint graphs $G_{1},\dots,G_{t}$, join the
underlying data structures that the algorithm uses for those graphs into a new
data structure for the graph $G=G_{1}\cup\dots\cup G_{t}$.

We call an algorithm (plus the underlying data structure) that supports these
operations an “incremental $k$-edge-connected components algorithm” (or “a
data structure for maintaining the $k$-edge-connected components”).

Now suppose that we are equipped with an incremental $k$-edge-connected
components algorithm. In order to efficiently maintain the decomposition tree
$\mathcal{T}$, we associate with every non-leaf node $N$ a data structure for
maintaining the $k$-edge-connected components. Furthermore, for every $k$-ecc
of $N$, we have a two-way correspondence between its label maintained by the
data structure and the child of $N$ that corresponds to it. Now suppose that
an edge $e$ is inserted to $N$. Then we use operation $(1)$ in order to find
the labels $C_{1},\dots,C_{t}$ of the $k$-eccs of $N$ that get merged due to
the insertion of $e$. If there is only one such $k$-ecc returned, there is
nothing to do. If all the $k$-eccs of $N$ are returned, then we make $N$ a
leaf node. Otherwise, we get from those labels the corresponding children of
$N$, we merge those children into a new child, and we establish a two-way
correspondence between this child and the new $k$-ecc of $N$ that is formed.
Furthermore, we retrieve the associated data structures of the children of $N$
that get merged, we join them into a new data structure using operation $(2)$,
and we associate the new data structure with the new child of $N$. Finally, we
insert the interconnection edges between $C_{1},\dots,C_{t}$ that we got from
operation $(1)$ into the new child of $N$. This completes the recursive
description of the update of $\mathcal{T}$ using an incremental $k$-edge-
connected components algorithm as a black box.

We will describe two different methods with which we can perform the merging
of nodes of $\mathcal{T}$, with a trade-off in time- and space-complexity. The
first method is the simplest one. Let $N$ be a node of $\mathcal{T}$, and let
$C_{1},\dots,C_{t}$ be the children of $N$ that we have to merge. Then we will
use the node with the greatest number of children among $C_{1},\dots,C_{t}$ as
the new node in which $C_{1},\dots,C_{t}$ get merged. So let $C$ be a node
among $C_{1},\dots,C_{t}$ with maximum number of children. Then we discard all
nodes in $\\{C_{1},\dots,C_{t}\\}\setminus\\{C\\}$, and we redirect the parent
pointer of their children to $C$. Since this involves at most $n$ nodes at
every level, and a parent pointer can be redirected at most $\log n$ times, we
get at most $O(n\log n)$ redirections of parent pointers at every level, and
$O(n^{2}\log n)$ redirections in total. In the second method we maintain all
nodes of $\mathcal{T}$ (possibly in a “deactivated” mode) throughout the
sequence of all insertions, and thus we may need as much as $\Omega(n^{2})$
space (since there are at most $O(n)$ insertions that can affect the
decomposition tree). The idea is to use a disjoint-set union data structure
$\mathit{DSU}_{i}$ [52] on the nodes of level $i$ of the tree, for all $i\geq
1$. In order to merge nodes at level $i$ we unite all of them using
$\mathit{DSU}_{i}$ and we choose one of them as the representative. We
consider the representative to be an _active_ node, in the sense that we can
use its parent pointer to move to level $i-1$, whereas the parent pointer of
the other nodes that got united will never be used again. Thus, in order to
access the parent of a node $N$ at level $i$, we use
$\mathit{find}_{i-1}(\mathit{parent}(N))$, where $\mathit{parent}$ denotes the
parent pointer in $\mathcal{T}$, and $\mathit{find}_{i-1}$ is the
$\mathit{find}$ operation of $\mathit{DSU}_{i-1}$. Notice that this approach
has the advantage that it does not explicitly redirect the parent pointers.
Using an optimal implementation for $\mathit{DSU}_{i}$ [52], we can perform
any sequence of $m$ operations $\mathit{find}_{i}$ or $\mathit{unite}_{i}$ in
$O(m\alpha(m,n))$ time in total. Since at most $n$ $\mathit{unite}$ operations
can take place at each level, we have an $O(n\alpha(n,n))$ time-bound at every
level for the mergings, and an $O(n^{2}\alpha(n,n))$ time-bound in total.

We note that the $n^{2}$ expression in the time-bound is an inherent
bottleneck of this approach for maintaining the maximal $k$-edge-connected
subgraphs, for any $k\geq 3$. In order to demonstrate this, let us introduce
some concepts. We call the edges that connect two different maximal $k$-edge-
connected subgraphs of a graph _$k$ -interconnection_ edges. Then we partition
the $k$-interconnection edges into levels as follows. If an edge participates
in a $k^{\prime}$-edge cut of the graph, for $k^{\prime}<k$, we define the
level of this edge to be $1$. Now suppose that we have defined all $d$-level
edges, for some $d\geq 1$. Then an edge that participates in a
$k^{\prime}$-edge cut of (a connected component of) the graph that remains
after we remove all $d^{\prime}$-level edges, for $d^{\prime}\leq d$, is
assigned level $d+1$. Now we observe that our method for updating the
decomposition tree explicitly maintains the levels of the $k$-interconnection
edges (because every $d$-level $k$-interconnection edge is essentially
maintained in the associated data structure of a node of depth $d$ of the
decomposition tree). There are sequences of insertions of edges in which
$\Omega(n)$ insertions may force $\Omega(n)$ edges to change their level, and
thus we need at least $\Omega(n^{2})$ time in total to maintain the
decomposition tree. An example for $k=3$ is shown in Figure 3. (This
generalizes easily to any $k>3$.)

Figure 3: An example of a sequence of insertions that can force $\Omega(n)$
$3$-interconnection edges to increase their level by one $\Omega(n)$ times.
The sequence of insertions, starting from the empty graph with vertices in
$\\{1,\dots,n\\}$ is
$(1,2),(1,2),(3,1),(3,2),(4,2),(4,3),\dots,(k,k-2),(k,k-1),\dots,(n,n-2),(n,n-1)$.
After the insertion of $(k,k-1)$, we have that $(k,k-1)$ and $(k,k-2)$ are the
only $1$-level edges, and the level of the other edges $(1,2),\dots,(k-1,k-2)$
increases by one. Note that $\\{1,\dots,k-1\\}$ is a $3$-edge-connected
component at this point, whereas all the maximal $3$-edge-connected subgraphs
are trivial.

###  3.3 The decomposition tree of the maximal $3$-edge-connected subgraphs

Here we apply the framework outlined in the previous section for the special
case $k=3$. We focus on the case $k=3$ for the following reasons. $(1)$ There
exist very efficient/asymptotically optimal algorithms for the incremental
maintenance of the $3$-edge-connected components that we can use for
maintaining the decomposition tree for the case $k=3$. $(2)$ Although there
exist very efficient algorithms for maintaining also the $4$\- and $5$-edge-
connected components [18, 15], and they seem applicable in our framework, they
involve a lot of technicalities and it would be very tedious to show how to
extend them in order to apply them for our purposes. For $k>5$ we are not even
aware of any efficient incremental algorithms that we could apply.222The fully
dynamic algorithm of Jin and Sun [36] seems very difficult to be usable in our
framework, because it does not explicitly maintain the $k$-edge-connected
components. $(3)$ The case $k=3$ is the simplest one to consider. And yet,
even here, we have to extend appropriately the existing data structures and
algorithms, and this involves various technicalities.

For the case $k=3$ we incorporate the algorithms of [27, 41, 40, 57], for
maintaining the $3$-eccs, in the decomposition tree. Thus, since these
algorithms basically maintain the $2$-eccs of the $1$-eccs, and the $3$-eccs
of the $2$-eccs, we augment the decomposition tree with more levels in order
to capture the decomposition into all $k^{\prime}$-eccs, for $k^{\prime}\leq
3$. To be more precise, we consider the decomposition tree $\mathcal{T}$ of
the maximal $3$-edge-connected subgraphs of $G$ that is formed by repeatedly
removing all $1$\- and $2$-edge cuts. The nodes of $\mathcal{T}$ correspond to
subgraphs of $G$. First, the root of $\mathcal{T}$ corresponds to the entire
graph. If $G$ is $3$-edge-connected, then this is the only node of
$\mathcal{T}$, and the decomposition is over. Otherwise, the children of the
root correspond to the connected components of $G$, which we call $1$-ecc
nodes. Then the children of every $1$-ecc node correspond to its $2$-edge-
connected components, and we call them $2$-ecc nodes. Finally, the children of
every $2$-ecc node correspond to its $3$-edge-connected components and we call
them $3$-ecc nodes. Now, if a $3$-ecc node corresponds to a $3$-edge-connected
subgraph of $G$, then it is a leaf of $\mathcal{T}$, and a maximal $3$-edge-
connected subgraph of $G$. Otherwise, it becomes the root of a subtree of
$\mathcal{T}$ that is produced recursively with the same procedure. In this
way, we compute the decomposition tree $\mathcal{T}$ of the maximal $3$-edge-
connected subgraphs of $G$. (See Figure 4 for an example.)

Figure 4: The decomposition tree $\mathcal{T}$ of the graph $G$ of Figure 1.
Notice the correspondence between the nodes of $\mathcal{T}$ and some
subgraphs of $G$. The leaves of $\mathcal{T}$ (coloured in black) correspond
to the maximal $3$-edge-connected subgraphs of $G$.

Observe that the size of $\mathcal{T}$ is $O(n)$,333However, in order to
efficiently maintain $\mathcal{T}$ after the insertion of new edges to $G$, we
may have to attach more information to $\mathcal{T}$, so that its total size
will be $O(n^{2})$. (See Section 4.2.) since the children of every node $N$ of
$\mathcal{T}$ correspond to subgraphs of the graph corresponding to $N$ that
partition its vertex set (and although some nodes have only one child, by
construction this child must have at least two children or two grandchildren,
unless it is a leaf). For convenience, and since no ambiguity arises, we
identify every node of $\mathcal{T}$ with the subgraph of $G$ that corresponds
to it. (We do not maintain this correspondence explicitly in any data
structure, as this would be impractically expensive in terms of space (and
therefore time). It is only a conceptual convention that we make, and we will
use it extensively in the sequel.) Furthermore, since $\mathcal{T}$ is rooted,
we let the nodes of $\mathcal{T}$ be partitioned into levels according to
their depth, where the level of the root is $0$. Thus we may speak of a
subgraph of $G$ at some level of $\mathcal{T}$. Observe that $\mathcal{T}$
contains $3k$ levels, for some $k\geq 0$, and that every maximal $3$-edge-
connected subgraph of $G$ is contained at some level $3k^{\prime}$, for
$k^{\prime}\leq k$, as a leaf. It is useful to note that $\mathcal{T}$
satisfies the following.

######  Property 3.4.

If we shrink a maximal $3$-edge-connected subgraph of $G$ into a single
vertex, then the decomposition tree of the resulting graph is given again by
$\mathcal{T}$.

Now we will give a high-level description of the changes that $\mathcal{T}$
undergoes when a new edge $(x,y)$ is inserted to $G$. Theorem 3.3 implies that
at most $3n-3$ insertions of edges may affect the decomposition tree, in any
sequence of edge insertions, where $n$ is the total number of vertices
inserted. By Property 3.4, we have that a newly inserted edge can affect the
decomposition tree only if its endpoints lie in different maximal $3$-edge-
connected subgraphs of $G$. Thus we consider the nearest common ancestor $N$
of the maximal $3$-edge-connected subgraphs of $G$ that contain $x$ and $y$.
This corresponds to the deepest node in the decomposition tree that contains
both $x$ and $y$, and it should be clear that the insertion of $(x,y)$ affects
only the decomposition of $N$. We distinguish three different cases, depending
on whether $(1)$ $N$ is the root or a $3$-ecc node, or $(2)$ $N$ is a $1$-ecc
node, or $(3)$ $N$ is a $2$-ecc node. The whole procedure is summarized in
Algorithm 1.

####  3.3.1 $N$ is the root or a $3$-ecc node

In this case $(x,y)$ joins two different connected components $C_{1}$ and
$C_{2}$ of $N$, and so it becomes a bridge of $N$ that connects them. Thus we
only have to merge $C_{1}$ and $C_{2}$ into a new $1$-ecc node (see Fig. 5).

Figure 5: Here we show the changes to the decomposition tree on the insertion
of the edge $(x,y)$. The nearest common ancestor $N$ of (the maximal $3$-edge-
connected subgraphs that contain) $x$ and $y$ is a $3$-ecc node. Therefore, we
need to know the two children of $N$ that contain $x$ and $y$; then we
retrieve the associated trees, join them properly with (an equivalent of) the
edge $(x,y)$, and then we merge the two nodes. Finally, we associate with it
the new tree that has been formed. In this figure, the middle graphs show the
decomposition of the graph into $3$-edge-connected components at every level.
Also, in the decomposition trees, we can see the trees associated with the
nodes we have to merge and the tree associated with the merged node. (The new
edge $(x,y)$ is stored inside this tree.) The $3$-edge-connected components
are highlighted with pink colour. Lower intensity signifies greater depth in
the decomposition tree.

####  3.3.2 $N$ is a $1$-ecc node

In this case $(x,y)$ joins two different $2$-edge-connected components $C_{1}$
and $C_{2}$ of $N$. Without loss of generality, assume that $x\in C_{1}$ and
$y\in C_{2}$. Let $T$ be tree of the $2$-edge-connected components of $N$, and
let $P=X_{1},\dots,X_{k}$ be the path on $T$ with endpoints $C_{1}$ and
$C_{2}$. (Thus we have $X_{1}=C_{1}$ and $X_{k}=C_{2}$.) Then the vertices
that are contained in $X_{1},\dots,X_{k}$ become $2$-edge-connected, and for
every pair of vertices not both of which belong to $X_{1}\cup\dots\cup X_{k}$
the edge-connectivity remains the same. Furthermore, for every
$i\in\\{1,\dots,k-1\\}$, let $(x_{i},y_{i})$ be the bridge of $N$ that
corresponds to the edge $(X_{i},X_{i+1})$ of $P$, and let also
$(x,y)=(y_{0},x_{k})$ (this is for notational convenience). Then, every pair
of edges in $\\{(x_{i},y_{i})\mid i\in\\{1,\dots,k-1\\}\\}\cup\\{(x,y)\\}$ is
a $2$-edge cut of $N$. Thus we have to merge all $2$-ecc nodes
$X_{1},\dots,X_{k}$ into a new $2$-ecc node $C$, and no change takes place on
$\mathcal{T}$ outside the subtree of $C$.

Now we have to consider the changes that possibly take place in the subtree of
$C$. For every $i\in\\{1,\dots,k\\}$, let $S_{i}$ be the cactus of the
$3$-edge-connected components of $X_{i}$, and let $Q_{i}$ be the cycle-path on
$S_{i}$ with endpoints the $3$-ecc of $X_{i}$ that contains $y_{i-1}$ and the
$3$-ecc of $X_{i}$ that contains $x_{i}$. Let also
$D_{(i,1)},\dots,D_{(i,t(i))}$ be the subgraphs of $X_{i}$ that correspond to
the nodes of $Q$. Then, the vertices that are contained in
$D_{(i,1)},\dots,D_{(i,t(i))}$ become $3$-edge-connected; furthermore, for
every pair of vertices of $X_{i}$ not both of which lie in
$D_{(i,1)}\cup\dots\cup D_{(i,t(i))}$ the edge-connectivity remains the same.
Thus we have to merge all $D_{(i,1)},\dots,D_{(i,t(i))}$ into a new $3$-ecc
node $D_{i}$; furthermore, no change in the subtree of $X_{i}$ takes place
outside the subtree of $D_{i}$. Now we have to consider the graphs
$D_{(i,1)},\dots,D_{(i,t(i))}$ as the connected components of the new graph
$D_{i}$. However, in order to maintain the decomposition subtree of $D_{i}$ on
$\mathcal{T}$, we have to take care of two things. First, some graphs
$D_{(i,j)}$, for $j\in\\{1,\dots,t(i)\\}$, might be leaves (prior to the
insertion of $(x,y)$). This means that they are $3$-edge-connected subgraphs,
and so we have to include them in the subtree of $D_{i}$ by expanding their
corresponding nodes on $\mathcal{T}$ with the addition of three intermediary
nodes. And secondly, there might exist edges in $X_{i}$ that connect some of
$D_{(i,1)},\dots,D_{(i,t(i))}$. (Note that these edges correspond naturally to
those of $S_{i}$ that connect the nodes of $Q_{i}$.) These edges are now
included in $D_{i}$, and so we have to consider their effect on the
decomposition subtree of $D_{i}$. Thus, in order to capture fully the effect
on $\mathcal{T}$ of the insertion of $(x,y)$, we have to re-insert those edges
to $G$. Observe that these edges constitute parts of $1$\- or $2$-edge cuts of
$D_{i}$, and so they will be re-inserted only once in order to perform the
insertion of $(x,y)$. However, their re-insertion may force other edges of
$G$, that lie in graphs on deeper levels, to be re-inserted to $G$.
Nevertheless, the nearest common ancestor involved in each such re-insertion
will either be a $3$-ecc or a $1$-ecc node. As a consequence, we note that no
new maximal $3$-edge-connected subgraphs will be formed after the insertion of
$(x,y)$ to $G$. Figure 6 is an example of this case.

Figure 6: Here we insert the edge $(x,y)$ to the graph. This joins two
different $2$-edge-connected components (at the first decomposition level),
which lie in the tree $T$ associated with the nearest common ancestor of
$\mathbf{x}$ and $\mathbf{y}$. The path of those $2$-eccs on $T$ consists of
three nodes, which we have to merge. So first we have to retrieve their
associated cactuses (which are shown in this figure), to merge some of their
nodes using $\mathtt{merge3ecc}$, and then to join them on a new cactus using
(essentially) the edges of the cycle. Here we can see the effect of
$\mathtt{merge3ecc}$ on the three cactuses. With gray are shown the nodes that
we have to merge. The resulting three cactuses get joined on their gray
(compressed) nodes along the edges of the triangle, one of which is
(essentially) the new one, and the other two lay on a higher level (inside the
tree $T$ of the $2$-eccs). Thus, those two edges got pushed down one level.
Also notice that the height of the decomposition tree increased.

We refer to the three step process of $(a)$ merging all
$D_{(i,1)},\dots,D_{(i,t(i))}$ into a single node $D_{i}$, $(b)$ expanding
every node $D_{(i,j)}$ that is a leaf, for $j\in\\{1,\dots,t(i)\\}$, with the
addition of three intermediary nodes, and $(c)$ re-inserting into $G$ the
inter-edges between the subgraphs $D_{(i,1)},\dots,D_{(i,t(i))}$ of $X_{i}$,
as _merging_ the $3$-ecc nodes $D_{(i,1)},\dots,D_{(i,t(i))}$ into $D_{i}$.
This procedure is shown in Algorithm 2. (The variable “parent” in Lines 2, 2
and 2 denotes the parent relation of $\mathcal{T}$.)

####  3.3.3 $N$ is a $2$-ecc node

In this case $(x,y)$ joins two different $3$-edge-connected components $C_{1}$
and $C_{2}$ of $N$. We note that this is the only case in which the formation
of new maximal $3$-edge-connected subgraphs of $G$ may take place (by merging
together smaller maximal $3$-edge-connected subgraphs of $G$). Let $S$ be
cactus of the $3$-edge-connected components of $N$, and let
$Q=X_{1},\dots,X_{k}$ be the cycle-path on $S$ with endpoints $C_{1}$ and
$C_{2}$. Then the vertices that are contained in $X_{1},\dots,X_{k}$ become
$3$-edge-connected, and for every pair of vertices not both of which belong to
$X_{1}\cup\dots\cup X_{k}$ the edge-connectivity remains the same. Thus, if
$Q$ contains all the nodes of $S$, then $N$ becomes $3$-edge-connected.
Therefore, if $N$ prior to the insertion of $(x,y)$ was the only $2$-edge-
connected component of its grandparent $R$ on $\mathcal{T}$, then this means
that $R$ becomes $3$-edge-connected, and so its subtree on $\mathit{T}$ is
condensed into $R$. Otherwise, all the proper descendants of $N$ are condensed
into a new single $3$-ecc node of $\mathcal{T}$, which corresponds to the new
maximal $3$-edge-connected subgraph that has been formed.

Now suppose that $Q$ does not contain all the nodes of $S$. Then we have to
perform a merging of the $3$-ecc nodes $X_{1},\dots,X_{k}$ into a new node
$D$, and then repeat the insertion of the edge $(x,y)$. Let $X$ and $Y$ be the
maximal $3$-edge-connected subgraphs of $G$ that contain $x$ and $y$,
respectively. Then the nearest common ancestor of $X$ and $Y$ on $\mathcal{T}$
is a descendant of $D$, and it can either be a $3$-ecc node or a $1$-ecc node
(in which case we are work as previously), or a $2$-ecc node again. In the
last case, either the formation of a new maximal $3$-edge-connected subgraph
of $G$ will take place (and we are done), or we will have to merge again some
$3$-ecc nodes of $\mathcal{T}$ into a new node and then repeat the insertion
of $(x,y)$. Observe that, eventually, this process must terminate, since every
time that we have to merge some $3$-ecc nodes into a new node, we leave some
of their siblings on the same level, and then the computation involves only
the subtree of the new node.

Figure 7 is a simple example of this case, where the whole graph becomes
$3$-edge-connected.

Figure 7: This is a simple example where the insertion of a new edge $(x,y)$
makes the whole graph $3$-edge-connected. This happens immediately, because
the nearest common ancestor $N$ of $x$ and $y$ is a $2$-ecc node, where the
associated cactus is the cycle-path connecting the nodes that contain $x$ and
$y$. Thus we merge all leaves of $N$, we discard the whole subtree $N$, and
assign as a child of $N$ the new maximal $3$-edge-connected subgraph that has
been formed. Notice that the parent of $N$ has only one child, and the parent
of the parent of $N$ has again only one child. Thus, we replace the
grandparent of $N$ with the child of $N$, and we discard $N$, its parent, and
its grandparent.

1 procedure $\mathtt{insert}(x,y)$

2 begin

3 $X\leftarrow$ the leaf of $\mathcal{T}$ that contains $x$

4 $Y\leftarrow$ the leaf of $\mathcal{T}$ that contains $y$

5 $N\leftarrow$ the nearest common ancestor of $X$ and $Y$ on $\mathcal{T}$

6 $C_{1}\leftarrow$ the child of $N$ that contains $x$

7 $C_{2}\leftarrow$ the child of $N$ that contains $y$

8 if  _$N$ is the root of $\mathcal{T}$ or a $3$-ecc node_ then

9 merge $C_{1}$ and $C_{2}$ into a new $1$-ecc node

10

11 end if

12 else if  _$N$ is a $1$-ecc node_ then

13 $T\leftarrow$ the tree of the $2$-edge-connected components of $N$

14 $X_{1},\dots,X_{k}\leftarrow$ the path on $T$ with endpoints $C_{1}$ and
$C_{2}$

15 foreach  _$i\in\\{1,\dots,k-1\\}$_ do

16 $(x_{i},y_{i})\leftarrow$ the edge of $N$ that corresponds to
$(X_{i},X_{i+1})$ of $T$

17

18 end foreach

19 $(y_{0},x_{k})\leftarrow(x,y)$

20 foreach  _$i\in\\{1,\dots,k\\}$_ do

21 $S_{i}\leftarrow$ the cactus of the $3$-edge-connected components of
$X_{i}$

22 $D_{(i,1)},\dots,D_{(i,t(i))}\leftarrow$ the cycle-path on $S_{i}$ with
endpoints the $3$-ecc of $X_{i}$ that contains $y_{i-1}$ and the $3$-ecc of
$X_{i}$ that contains $x_{i}$

23 $\mathtt{merge3ecc}(D_{(i,1)},\dots,D_{(i,t(i))})$

24

25 end foreach

26 merge all $X_{1},\dots,X_{k}$ into a new $2$-ecc node of $\mathcal{T}$

27

28 end if

29 else if  _$N$ is a $2$-ecc node_ then

30 $S\leftarrow$ the cactus of the $3$-edge-connected components of $N$

31 $D_{1},\dots,D_{k}\leftarrow$ the cycle-path on $S$ with endpoints $C_{1}$
and $C_{2}$

32 if  _$V(S)=\\{D_{1},\dots,D_{k}\\}$_ then

33 $R\leftarrow$ the grandparent of $N$ on $\mathcal{T}$

34 if  _$N$ is the only $2$-ecc of $R$_ then condense the subtree of $R$ into
$R$

35 else condense all the proper descendants of $N$ into a new $3$-ecc node

36

37 end if

38 else

39 $\mathtt{merge3ecc}(D_{1},\dots,D_{k})$

40 $\mathtt{insert}(x,y)$

41

42 end if

43

44 end if

45

46 end

47

Algorithm 1 Update the decomposition tree $\mathcal{T}$ after inserting the
edge $(x,y)$ to $G$

1 procedure $\mathtt{merge3ecc}(D_{1},\dots,D_{k})$

2 begin

3 for  _$i\in\\{1,\dots,k\\}$_ do

4 if  _$D_{i}$ is a leaf of $\mathcal{T}$_ then

5 let $D_{i}^{\prime}$, $D_{i}^{\prime\prime}$ and
$D_{i}^{\prime\prime\prime}$ be a new $1$-ecc, $2$-ecc and $3$-ecc node,
respectively, where $D_{i}^{\prime}$, $D_{i}^{\prime\prime}$ and
$D_{i}^{\prime\prime\prime}$ correspond to the same graph as $D_{i}$

6 $\mathit{parent}(D_{i}^{\prime\prime\prime})\leftarrow D_{i}^{\prime\prime}$

7 $\mathit{parent}(D_{i}^{\prime\prime})\leftarrow D_{i}^{\prime}$

8 $\mathit{parent}(D_{i}^{\prime})\leftarrow D_{i}$

9

10 end if

11

12 end for

13 $S\leftarrow$ the cactus of the $3$-edge-connected components of $X$

14 $\mathcal{E}\leftarrow$ the edge set of $S[D_{1}\cup\dots\cup D_{k}]$

15 merge all $D_{1},\dots,D_{k}$ into a new $3$-ecc node

16 foreach  _edge $e$ in $\mathcal{E}$_ do

17 $\mathtt{insert}(e)$

18

19 end foreach

20

21 end

22

Algorithm 2 merge the children $D_{1},\dots,D_{k}$ of a $2$-ecc node $X$

##  4 Maintaining the decomposition tree after insertions

As seen in Algorithms 1 and 2, in order to efficiently update $\mathcal{T}$
after inserting an edge $(x,y)$ to $G$, we have to provide efficient
implementations for the following procedures:

  1. (1)

Find the leaves $X$ and $Y$ of $\mathcal{T}$ that contain $x$ and $y$,
respectively.

  2. (2)

Find the nearest common ancestor $N$ of $X$ and $Y$ on $\mathcal{T}$.

  3. (3)

Find the grandchild of $N$ that contains a particular vertex $v\in N$. (This
is needed in Line 1 of Algorithm 1, in order to find the $3$-eccs of $X_{i}$
that contain $y_{i-1}$ and $x_{i}$.)

  4. (4)

Merge sets of nodes of $\mathcal{T}$ (lying on the same level) into a new
single node.

  5. (5)

Find the nodes of $\mathcal{T}$ that have to get merged, and the inter-
connection edges between the subgraphs that correspond to them.

We will provide two different solutions for this set of procedures. In Section
4.1 we rely on the ideas and the data structures of [27, 41, 57], in order to
provide an algorithm that uses $O(n)$ space and runs in
$O(n^{2}\log^{2}n+m\alpha(m,n))$ time, for any sequence of $m$ edge and $n$
vertex insertions. In Section 4.2 we rely on [41] and [40], in order to
provide an algorithm that uses $O(n^{2})$ space and runs in
$O(n^{2}\alpha(n,n)+m\alpha(m,n))$ time, for any sequence of $m$ edge and $n$
vertex insertions. We note that the first algorithm is more readily amenable
to implementations. The second algorithm, although it is asymptotically more
time-efficient, it uses the sophisticated data structures of [40] (summarized
and expanded in Section 6), and it may be less efficient than the first
algorithm in practice.

In both algorithms we use the same solution for $(1)$: an optimal disjoint set
union data structure $DSU_{3ecs}$ [52], that operates on $V(G)$, and uses as
representatives the leaves of $\mathit{T}$ (which correspond bijectively to
the maximal $3$-edge-connected subgraphs of $G$). $DSU_{3ecs}$ supports the
operations $\mathit{find_{3ecs}}(x)$ and $\mathit{unite_{3ecs}}(x,y)$.
$\mathit{find_{3ecs}}(x)$ returns a pointer to the maximal $3$-edge-connected
subgraph of $G$ that contains $x$, and $\mathit{unite_{3ecs}}(x,y)$ unites the
sets of vertices of the maximal $3$-edge-connected subgraphs of $G$ that
contain $x$ and $y$. $DSU_{3ecs}$ uses $O(n)$ space, and it can perform any
sequence of $m$ operations $\mathit{find_{3ecs}}$ and $\mathit{unite_{3ecs}}$
in $O(m\alpha(m,n))$ time in total [52]. (Thus we get this expression in the
time-bounds of both algorithms.)

Furthermore, for $(5)$ we rely on data structures associated with the nodes of
$\mathcal{T}$, that represent trees or cactuses. In particular, recall that
(the graph corresponding to) every $1$-ecc node $X$ is a connected component
of (the graph corresponding to) its parent, and the children of $X$ correspond
to its $2$-edge-connected components. Thus, we associate with every $1$-ecc
node a data structure that represents the tree of its $2$-edge-connected
components. This data structure is used in order to find the children of $X$
that we have to merge (in Line 1 of Algorithm 1), and the inter-connection
edges between (the graphs that correspond to) those children (in Line 1 of
Algorithm 1). Similarly, every $2$-ecc node $X$ has an associated data
structure that represents the cactus of its $3$-edge-connected components.
This data structure is used in order to find the children of $X$ that we have
to merge (in Lines 1 and 1 of Algorithm 1), and the inter-connection edges
between (the graphs that correspond to) those children (in Line 2 of Algorithm
2). More details about the operations supported by these data structures will
be given in Section 4.1.

Finally, we note that the $O(n^{2})$ expression in the time-bounds of both
algorithms is a bottleneck in their total running time. In fact, Lines 1 and 1
of Algorithm 1 and Line 2 of Algorithm 2 may create a sequence of recursive
calls, so that, even for a single edge insertion, we may have to perform
$O(n^{2})$ re-insertions of already inserted edges. However, since by Theorem
3.3 there are only $O(n)$ edge insertions that can affect the decomposition
tree, and every re-insertion (performed internally by the algorithm) can only
affect deeper levels than before, and there can be only $O(n)$ levels in the
decomposition tree, we have that any sequence of edge insertions to $G$ can
initiate at most $O(n^{2})$ calls to procedure $\mathtt{insert}$ of Algorithm
1.

###  4.1 An $O(n^{2}\log^{2}n+m\alpha(m,n))$-time algorithm for the
incremental maintenance of $\mathcal{T}$

An efficient solution for $(2)$ is to use the top-trees data structure of
Alstrup et al. [4]. With this data structure we can perform nearest common
ancestor queries in dynamic trees with $n$ nodes in amortized $O(\log n)$ time
per query. Furthermore, with top-trees we can also answer level ancestor
queries within the same time-bounds. Thus we can solve $(3)$ efficiently with
a query for the $d+2$ level ancestor of $V$, where $V$ is the leaf of
$\mathcal{T}$ that contains $v$, and $d$ is the level of $N$. (We may assume
that every node of $\mathcal{T}$ has an attribute for its level on
$\mathcal{T}$.)

The merging of nodes in $(4)$ can be performed by redirecting the parents of
the children of the nodes with the least number of children to the node with
the most number of children (breaking ties arbitrarily), and then discarding
these nodes. (We may assume that every node of $\mathcal{T}$ has an attribute
for its number of children.) In other words, suppose that we have to merge the
nodes $X_{1},\dots,X_{k}$, where $X_{1}$ has the greatest number of children
among $X_{1},\dots,X_{k}$. Then we redirect the parents of the children of
$X_{2},\dots,X_{k}$ to $X_{1}$, and then we discard $X_{2},\dots,X_{k}$ (and
all the information associated with them). Since the nodes of every level of
$\mathcal{T}$ are $O(n)$, this procedure ensures that at most $O(n\log n)$
redirections can take place in total in every level. However, for every such
redirection, a deletion and an insertion of an edge of $\mathcal{T}$ must take
place, and this takes $O(\log n)$ amortized time using the top-trees. Thus we
get an $O(n\log^{2}n)$ time-bound for every level of $\mathcal{T}$, and since
there are at most $O(n)$ levels in $\mathcal{T}$, we get the
$O(n^{2}\log^{2}n)$ time-bound in total.

Now, for $(5)$, we assume, as above, that every $1$-ecc node has an associated
data structure that represents the tree of its $2$-edge-connected components,
and every $2$-ecc node has an associated data structure that represents the
cactus of its $3$-edge-connected components. We use the associated data
structures for the trees of the $2$-edge-connected components in order to be
able to perform efficiently the following. In Line 1 of Algorithm 1, we access
the associated data structure $T$ of $N$, in order to find its children
$X_{1},\dots,X_{k}$ that we have to merge in Line 1. Thus we assume that the
data structure for trees supports the operation
$\mathtt{compressPath(T,x,y)}$, which, given a pointer $T$ to a tree, and
pointers $x$ and $y$ to nodes of this tree, it finds the simple path $P$ that
connects these nodes on the tree, returns pointers to the nodes of $P$ and the
edges of $P$, and then merges all nodes of $P$ into a new node and also
returns a pointer to this node. We assume that the nodes and the edges of $T$
have some information associated with them. Specifically, since every edge $e$
of $T$ corresponds essentially to a bridge of $N$, and this bridge is an edge
$(x,y)$ of $G$, we let $e$ point to the edge $(x,y)$ of $G$. This information
is needed for Lines 1 and 1. Furthermore, since every node $v$ of $T$
corresponds essentially to a child $V$ of $N$, we let $v$ point to $V$. This
is used precisely in order to find the children $X_{1},\dots,X_{k}$ of $N$
that we have to merge. Conversely, every child of $N$ must point to its
corresponding node of $T$, in order to be able to find the endpoints of the
path on $T$ that we have to find with the call to $\mathtt{compressPath}$.
Finally, since we may have to merge some children of the root or of a $3$-ecc
node in Line 1 of Algorithm 1, we also have to link the associated
(representations of the) trees of those children, with the addition of an edge
that corresponds to the one that has been (re-)inserted to $G$. Specifically,
suppose that an edge $(x,y)$ is (re-)inserted to $G$, and that the nearest
common ancestor $N$ of $X$ and $Y$ is the root or a $3$-ecc node, where $X$
and $Y$ are the leaves of $\mathcal{T}$ that contain $x$ and $y$,
respectively. Let $C_{1}$ and $C_{2}$ the the children of $N$ that contain $x$
and $y$, respectively. Then, in Line 1, we have to merge $C_{1}$ and $C_{2}$
into a new $1$-ecc node $C$. Now, the data structure associated with $C$ must
represent a tree that is formed by linking the tree represented by the
associated data structure to $C_{1}$ with the tree represented by the
associated data structure to $C_{2}$, through the addition of an edge
$e=(u,v)$ with endpoints corresponding to the children of $C_{1}$ and $C_{2}$
that contain $x$ and $y$, respectively. (These children of $C_{1}$ and $C_{2}$
can be found with a query for the $d+2$ level ancestors of $X$ and $Y$,
respectively, where $d$ is the level of $N$.) Furthermore, since $e$
corresponds essentially to $(x,y)$, the associated information to $e$ must be
a pointer to $(x,y)$. Thus, the data structure for trees must support the
operation $\mathtt{joinTrees(T_{1},T_{2},(u,v))}$, which, given a pointer
$T_{1}$ to a (representation of a) tree $\tilde{T}_{1}$, a pointer $T_{2}$ to
a (representation of a) tree $\tilde{T}_{2}$, a pointer $u$ to a node
$\tilde{u}$ of $\tilde{T}_{1}$, a pointer $v$ to a node $\tilde{v}$ of
$\tilde{T}_{2}$, and some extra information to be associated with the edge
$(\tilde{u},\tilde{v})$, links the trees $\tilde{T}_{1}$ and $\tilde{T}_{2}$
through the addition of the edge $(\tilde{u},\tilde{v})$.

The associated data structures for the cactuses of the $3$-edge-connected
components of $2$-ecc nodes are used to perform the analogous operations that
are performed by the data structures for trees. Specifically, in Lines 1 and 1
of Algorithm 1, we access the associated data structure for the $3$-edge-
connected components of a node $X$ of $\mathcal{T}$, in order to find its
children that we have to merge later on (with a call to procedure
$\mathtt{merge3ecc}$). Thus we assume that the data structure for cactuses
supports the operation $\mathtt{compressCyclePath(S,x,y)}$, which, given a
pointer $S$ to a cactus, and pointers $x$ and $y$ to nodes of this cactus, it
finds the cycle-path $Q$ on $S$ with endpoints these nodes, it returns
pointers to the nodes of $Q$ and the edges of $S$ between the nodes of $Q$,
and then merges all nodes of $Q$ into a new node and also returns a pointer to
this node. We assume that the nodes and the edges of $S$ have some information
associated with them. Specifically, since every edge $e$ of $S$ corresponds
essentially to an edge of $X$, and this edge is an edge $(x,y)$ of $G$, we let
$e$ point to $(x,y)$. This information is needed for Line 2 of Algorithm 2.
Furthermore, since every node $v$ of $S$ corresponds essentially to a child
$V$ of $X$, we let $v$ point to $V$. This is used precisely in order to find
the children of $X$ that we have to merge. Conversely, every child of $X$ must
point to its corresponding node of $S$, in order to be able to find the
endpoints of the cycle-path on $S$ that we have to find with the call to
$\mathtt{compressCyclePath}$. Finally, since we may have to merge the children
$X_{1},\dots,X_{k}$ of the $1$-ecc node $N$ in Line 1 of Algorithm 1, we also
have to link the associated (representations of the) cactuses of those
children, with the addition of a cycle that corresponds to the one that has
been formed by the (re-)insertion of $(x,y)$ to $G$. Specifically, when we
merge $X_{1},\dots,X_{k}$ into a new $2$-ecc node $X$, the associated cactus
of $X$ must be that which is formed by joining the cactuses associated with
$X_{1},\dots,X_{k}$ with a cycle corresponding to $D_{1},\dots,D_{k}$, where
$D_{i}$, for $i\in\\{1,\dots,k\\}$, is the new $3$-ecc node that has been
formed by merging $D_{(i,1)},\dots,D_{(i,t(i))}$ through the call
$\mathtt{merge3ecc}$ in Line 1. Furthermore, the edges of the new cactus that
correspond to the edges $(D_{1},D_{2}),\dots,(D_{k-1},D_{k}),(D_{k},D_{1})$ of
$X$, must correspond to the edges
$(x_{1},y_{1}),\dots,(x_{k-1},y_{k-1}),(y,x)$. This information is needed in
Line 2 of Algorithm 2. Thus, the data structure for cactuses must support the
operation
$\mathtt{joinCactuses(S_{1},\dots,S_{k},(d_{1},d_{2}),\dots,(d_{k},d_{1}))}$,
which, given pointers $S_{1},\dots,S_{k}$ to (representations of) cactuses
$\tilde{S}_{1},\dots,\tilde{S}_{k}$, pointers $d_{1},\dots,d_{k}$ to nodes
$\tilde{d}_{1},\dots,\tilde{d}_{k}$ of $\tilde{S}_{1},\dots,\tilde{S}_{k}$,
respectively, and some extra information to be associated with the edges
$(\tilde{d}_{1},\tilde{d}_{2}),\dots,(\tilde{d}_{k},\tilde{d}_{1})$, links the
cactuses $\tilde{S}_{1},\dots,\tilde{S}_{k}$ through the addition of the cycle
$(\tilde{d}_{1},\tilde{d}_{2}),\dots,(\tilde{d}_{k},\tilde{d}_{1})$.

In Section 5 we provide efficient implementations for the associated data
structures for trees and cactuses. These implementations use size $O(n)$ for a
collection of trees or cactuses with $n$ nodes, and can perform any sequence
of operations in $O(n\log n)$ time in total. We use a data structure for trees
in every $3k+1$ level of the tree, and a data structure for cactuses in every
$3k+2$ level of the tree. Since the number of nodes of the trees (of the
$2$-eccs) or of the cactuses (of the $3$-eccs) that correspond to the nodes of
every level of $\mathcal{T}$ can be at most $n$, and there are at most $O(n)$
levels on $\mathcal{T}$, we thus have that the operations in the associated
data structures can take time $O(n^{2}\log n)$ in total for any sequence of
edge insertions to $G$.

Finally, Algorithm 3 shows how we can handle the insertion of a new vertex $v$
to $G$. We simply introduce three new nodes $C$, $C^{\prime}$, and
$C^{\prime\prime}$ (an $1$-ecc node, a $2$-ecc node, and a $3$-ecc node,
respectively), that correspond to $v$, and we set
$\mathit{parent}(C)\leftarrow\mathit{root}$,
$\mathit{parent}(C^{\prime})\leftarrow C$, and
$\mathit{parent}(C^{\prime\prime})\leftarrow C^{\prime}$. Since the leaf of
$\mathcal{T}$ that contains $v$ is $C^{\prime\prime}$, we also set the
representative $\mathit{find_{3ecs}}(v)\leftarrow C^{\prime\prime}$. We also
associate a (representation of a) trivial tree to $C$, and a (representation
of a) trivial cactus to $C^{\prime}$. The DSU data structure and the data
structures in Section 5 allow for new node insertions, and the same time-
bounds hold (where $n$ is interpreted as the total number of vertices that
will have been inserted to $G$ at the moment we estimate the time that it took
to perform all the operations of the algorithm so far).

1 procedure $\mathtt{insert}(v)$

2 begin

3 let $C$, $C^{\prime}$ and $C^{\prime\prime}$ be a new $1$-ecc, $2$-ecc and
$3$-ecc node, respectively

4 $\mathit{parent}(C)\leftarrow$ root of $\mathcal{T}$

5 $\mathit{parent}(C^{\prime})\leftarrow C$

6 $\mathit{parent}(C^{\prime\prime})\leftarrow C^{\prime}$

7 let the representative of $v$ in $\mathit{DSU_{3ecs}}$ be $C^{\prime\prime}$

8 initialize a new trivial tree $T$, and associate it with $C$

9 initialize a new trivial cactus $S$, and associate it with $C^{\prime}$

10

11 end

12

Algorithm 3 Update the decomposition tree $\mathcal{T}$ after inserting a new
vertex $v$ to $G$

###  4.2 An $O(n^{2}\alpha(n,n)+m\alpha(m,n))$-time algorithm for the
incremental maintenance of $\mathcal{T}$

Now we will describe a more time-efficient algorithm to handle insertions to
the graph. (This algorithm, however, uses $O(n^{2})$ space.) First, we can
handle the operations in $(5)$ exactly as we did in Section 4.1, although here
we use the more sophisticated data structures for trees and cactuses that are
described in Section 6. The implementations given in Section 6 use size $O(n)$
for a collection of trees or cactuses with $n$ nodes, and can perform any
sequence of operations in $O(n\alpha(n,n))$ time in total. Since we use a data
structure for trees in every $3k+1$ level, and a data structure for cactuses
in every $3k+2$ level, and there are at most $O(n)$ levels in $\mathcal{T}$,
we thus we get the $O(n^{2}\alpha(n,n))$ expression in the total time-bound .

To perform the merging of nodes in $(4)$ we use an optimal disjoint set union
data structure $DSU_{i}$ [52], on every level $i$ of $\mathcal{T}$, that
operates on the node set of that level and uses as representatives nodes on
that level that we consider to be “active”. The function of an active node is
to represent all the nodes that have been merged with it; initially, all nodes
of $\mathcal{T}$ are active, and, throughout, the parent pointer on
$\mathcal{T}$ exists only for the active nodes. $DSU_{i}$ supports the
operations $\mathit{find_{i}}(x)$ and $\mathit{unite_{i}}(x,y)$.
$\mathit{find_{i}}(x)$ returns a pointer to the active node that has been
merged with $x$, and $\mathit{unite_{i}}(x,y)$ merges the sets of nodes that
are represented by the active nodes $x$ and $y$, and sets as representative
one of $x$ or $y$ (while deactivating the other). Thus, in order to find the
parent of an active node $X$ of $\mathcal{T}$ on level $i$, we use
$\mathit{find_{i-1}}(\mathit{parent}(X))$. $DSU_{i}$ uses $O(n)$ space, and it
can perform any sequence of $m$ operations $\mathit{find_{i}}$ and
$\mathit{unite_{i}}$ in $O(m\alpha(m,n))$ time in total [52].

To perform efficiently the operations $(2)$ and $(3)$, we basically maintain,
for every inter-connection edge $e=(x,y)$ of $G$ (that is, for every edge $e$
whose endpoints, at the time of its insertion, lie in different maximal
$3$-edge-connected subgraphs of $G$), two paths of $\mathcal{T}$ whose nodes
contain an endpoint of $e$, that start from the leaves of $\mathcal{T}$ that
contain $x$ and $y$, and go up until at least their nearest common ancestor.
In order to achieve this, we augment the information associated with
$\mathcal{T}$ as follows. For every node $Z$ of $\mathcal{T}$ we associate a
linked list $L_{Z}$, where every element of $L_{Z}$ corresponds to an endpoint
of an inter-connection edge that lies in an ancestor of $Z$. Thus, the
existence of those lists means that we may need as much as $O(n^{2})$ space
(since the number of inter-connection edges can be at most $O(n)$, and the
number of levels of $\mathcal{T}$ is $O(n)$). Every element of $L_{Z}$ is a
pointer that points to an element of $L_{C}$, for some child $C$ of $Z$. Also,
every element of $L_{Z}$ has a pointer to $Z$ (so that we can find in constant
time the node in whose associated list this pointer lies). Thus we may say
that a pointer of $L_{Z}$ lies in $Z$. Finally, for every inter-connection
edge $e=(x,y)$, we maintain two pointers $e_{x}$ and $e_{y}$, that point to
the elements of a list $L_{Z}$, for some node $Z$ that contains both $x$ and
$y$.

Now we work as follows. Let $e=(x,y)$ be an edge that is inserted to $G$ for
the first time. (I.e., this is the first time that we call
$\mathtt{insert}(e)$ of Algorithm 1. Notice, of course, that an edge
$e^{\prime}=(x,y)$ may have previously been inserted to $G$, since we allow
for multiple edges. But now we consider $e$ as a new insertion. Furthermore,
we can easily determine whether $\mathtt{insert}(e)$ is the first time we call
$\mathtt{insert}$ on $e$, by using a flag every time we call $\mathtt{insert}$
from Line 1 of Algorithm 1 or Line 2 of Algorithm 2, in order to signify that
this is a re-insertion.) First we find the leaves $X$ and $Y$ of $\mathcal{T}$
that contain $x$ and $y$, respectively, by calling $\mathit{find_{3ecs}}(x)$
and $\mathit{find_{3ecs}}(y)$, respectively. Suppose that $X\neq Y$ (for
otherwise there is nothing to do). Then we crawl up the tree, starting from
$X$ and $Y$, by following the parents alternatingly, marking all the nodes
that we meet, and keeping them in a stack in order to unmark them later. When
we meet a node $N$ that is already marked, we have that this is the nearest
common ancestor of $X$ and $Y$ on $\mathcal{T}$, and we unmark all the nodes
that we traversed. Now we start again from $X$, and we follow the parents
until we reach $N$. For every node $Z$ that we traverse, including $N$, we
append a new pointer $Z_{(e,x)}$ to $L_{Z}$. If $Z=X$, then we let $Z_{(e,x)}$
point to $\mathit{null}$. Otherwise, let $C$ be the child of $Z$ that we
traversed before reaching $Z$; then we let $Z_{(e,x)}$ point to $C_{(e,x)}$.
We repeat the same process starting from $Y$. Finally, we let $e_{x}$ point to
$N_{(e,x)}$ and we let $e_{y}$ point to $N_{(e,y)}$. Observe that this process
may need as many as $O(n)$ calls to the parent function, and $O(n)$ pointer
manipulation operations. Thus, since the total number of first-time edge
insertion in any sequence of edge insertions is $O(n)$, and every call to the
parent function involves a call to $\mathit{find_{i}}$, for some $i$, the
total cost of this process in the running time of the algorithm is
$O(n^{2}\alpha(n,n))$.

Now suppose that we re-insert an edge $e=(x,y)$. Then we can find the nearest
common ancestor of the leaves $X$ and $Y$ of $\mathcal{T}$ that contain $x$
and $y$, respectively, by following the path of pointers starting from $e_{x}$
and $e_{y}$, and moving on to deeper levels in parallel, until we reach two
pointers that lie on two nodes $C$ and $D$ that have not got merged together,
in which case the common parent of $C$ and $D$ is the nearest common ancestor
of $X$ and $Y$ on $\mathcal{T}$. Then, since $C$ and $D$ will have to get
merged, we let $e_{x}$ point to $C_{(e,x)}$ and $e_{y}$ point to $D_{(e,y)}$,
in order to avoid traversing the same path of pointers again. Since the total
number of edges that can affect the decomposition tree, in any sequence of
edge insertions, is $O(n)$, and every time an edge is re-inserted it is moved
into deeper levels, observe that the total cost of this process in the running
time of the algorithm is $O(n^{2}\alpha(n,n))$. Now suppose that we want to
find the grandchild of $N$ that contains $x$. (We can follow the analogous
procedure in order to find the grandchild of $N$ that contains $y$.) Then we
can use the pointer $N_{(e,x)}$ stored in $L_{N}$. This points to a pointer
$C_{(e,x)}$ in $L_{C}$, for a node $C$ that is merged with a child
$C^{\prime}$ of $N$. And then $C_{(e,x)}$ points to $D_{(e,x)}$ in $L_{D}$,
for a node $D$ that is merged with a child $D^{\prime}$ of $C^{\prime}$. Thus
we can find $D$ in constant time, and then we can find $D^{\prime}$ with a
call $\mathit{find_{i}}(D)$, where $i$ is the level of $D$. Again, since there
can be at most $O(n^{2})$ re-insertions of edges, the total cost of this
process in the running time of the algorithm is $O(n^{2}\alpha(n,n))$.

All the data structures with which $\mathcal{T}$ is equipped (the DSU data
structures, and the associated data structures for trees and cactuses), allow
for new node insertions, and the same time-bounds hold. Thus, the insertion of
new vertices to $G$ is performed as shown in Algorithm 3.

##  5 Data structures for trees and cactuses

To maintain the decomposition tree of the maximal $3$-edge-connected
subgraphs, we will need the following two data structures, which we may use as
black boxes in the algorithm. They operate on collections of trees and
cactuses, respectively. We assume that there is some information associated
with every edge of every tree or cactus 444For our algorithm, this information
is a pointer to an edge of the original graph (whose maximal $3$-edge-
connected subgraphs we want to maintain)..

The first is a data structure that works on a collection of trees and supports
the following operations.

  * •

$\mathtt{compressPath(T,x,y)}$. Given a tree $T$ and nodes $x$ and $y$ on $T$,
this operation finds the simple path $P$ that connects $x$ and $y$ on $T$ and
compresses it into a new node $z$ (converting $T$ into a smaller tree).
Furthermore, it returns pointers to all nodes and (information associated with
the) edges on $P$, as well as to the new node $z$. Finally, if $(u,v)$ was an
edge of $T$, prior to the call of this operation, with $u\notin P$ and $v\in
P$, then $(u,z)$ (in the new tree) must contain the same information that was
previously associated with $(u,v)$.

  * •

$\mathtt{joinTrees(T_{1},T_{2},(x,y))}$. Given two trees $T_{1},T_{2}$ and
nodes $x\in T_{1}$ and $y\in T_{2}$, this operation links the trees $T_{1}$
and $T_{2}$ by introducing a new edge $(x,y)$.

The second data structure works on a collection of cactuses and supports the
following operations.

  * •

$\mathtt{compressCyclePath(S,x,y)}$. Given a cactus $S$ and nodes $x$ and $y$
on $S$, this operation finds the “cycle-path” $P$ that connects $x$ and $y$ on
$S$. It compresses all nodes on $P$ into a new node $z$ by properly squeezing
the involved cycles. Furthermore, it returns pointers to all nodes on $P$, to
all (information associated with the) edges that connect pairs of those nodes
(if there are any), as well as to the new node $z$. Finally, if $(u,v)$ was an
edge of $S$, prior to the call of this operation, with $u\notin P$ and $v\in
P$, then $(u,z)$ (in the new cactus) must contain the same information that
was previously associated with $(u,v)$.

  * •

$\mathtt{joinCactuses(S_{1},\dots,S_{k},(x_{1},x_{2}),\dots,(x_{k},x_{1}))}$.
Given a collection of cactuses $S_{1},\dots,S_{k}$ and nodes $x_{i}\in S_{i}$,
$i\in\\{1,\dots,k\\}$, this operation links the cactuses $S_{1},\dots,S_{k}$
into a larger cactus by introducing the edges
$(x_{1},x_{2}),\dots,(x_{k},x_{1})$ (which induce a new cycle).

In Sections 5.1 and 5.2, we provide implementations for data structures
maintaining trees and cactuses where we can perform any sequence of operations
in $O(n\log n)$ time, assuming that the total number of nodes is at most $n$.
To achieve this time-bound, we will draw ideas from [27], [41], and [57].
Using these datastructures, we spend an additional $O(n^{2}\log n)$ time for
the incremental maintenance of the decomposition tree. To see this, recall
that we use representations for the trees of the $2$-edge-connected components
at levels $3k+1$ of the decomposition tree (where $0\leq k<n$), and
representations for the cactuses of the $3$-edge-connected components at
levels $3k+2$ (where $0\leq k<n$). Then, every operation
$\mathtt{compressPath}$, $\mathtt{joinTrees}$, $\mathtt{compressCyclePath}$
and $\mathtt{joinCactuses}$ is performed on structures on the same level.
Since there are $O(n)$ levels on which these operations may be performed, and
the total number of nodes at any level is $O(n)$, we get the $O(n^{2}\log n)$
time bound.

In Section 6, we use the more sophisticated implementations for those data
structures provided by [40], in order to get a $O(n\alpha(n,n))$-time bound
for performing any sequence of operations on trees or cactuses (on the same
level), which gives $O(n^{2}\alpha(n,n))$ in the total time bound of the
algorithm for maintaining the decomposition tree.

###  5.1 An implementation for trees

(a) Representation

An idea is to represent the trees as rooted trees. For every node $x$ we let
$p(x)$ denote its parent (if $x$ is the root, we leave $p(x)$ undefined).
Also, every node $x$ has a pointer $x.\mathit{edge}$ to the edge $(x,p(x))$
that connects $x$ with its parent. We use a DSU data structure to perform
mergings of nodes. The DSU data structure supports the operations
$\mathit{find}(x)$ and $\mathit{unite}(x,y)$. Thus, in order to access the
parent of node $x$ we actually use $\mathit{find}(p(x))$ (although we will not
write this explicitly in what follows).

(b) Operations

We execute $\mathit{compressPath}(T,x,y)$ as follows. We start from $x$ and
$y$, and we alternatingly climb up the tree following the parents, marking all
nodes that we traverse, until we meet an already marked node $z$. (This
ensures that we traverse at most $2d-1$ nodes, where $d$ is the number of
nodes of the simple path connecting $x$ and $y$.) Then there are two
possibilities: either $(1)$ $z=x$ or $z=y$, or $(2)$ $z$ is neither $x$ nor
$y$. In the first case, assuming w.l.o.g. that $z=y$, the path that we have to
compress consists of the nodes $x,p(x),p(p(x)),\dots,y$. In the second case,
the path consists of two parts: $x,p(x),\dots,z$ and $y,p(y),\dots,z$. In case
$(1)$ we work as follows. We start from $x$; we retrieve the edge $(x,p(x))$
(using the pointer stored in $x$), we call $\mathit{unite}(x,p(x))$, setting
as representative of the new set $p(x)$, and we repeat, until we reach $z=y$.
In case $(2)$ we work as in case $(1)$ twice, starting from both $x$ and $y$,
until we reach $z$ each time.

The $\mathit{joinTrees}(T_{1},T_{2},(x,y))$ operation works as follows. First,
we determine which of $T_{1},T_{2}$ is smaller (w.r.t. its number of nodes).
This can be done easily if we maintain for every tree an attribute
$\mathit{size}$ indicating the number of its nodes. Assume w.l.o.g. that the
smallest tree is $T_{1}$ (or that its size is equal to that of $T_{2}$). Then
we reroot $T_{1}$ at $x$, and we set $p(x)\leftarrow y$,
$x.\mathit{edge}\leftarrow(x,y)$, and $T_{2}.\mathit{size}\leftarrow
T_{2}.\mathit{size}+T_{1}.\mathit{size}$. The rerooting of $T_{1}$ at $x$ is
performed as follows. First we find the path $P$ connecting $x$ with the root
$r$ of $T_{1}$, by following the parents. Then we process the nodes of $P$ in
reverse order, starting from $r$ until we reach $x$ (which we do not process),
and we simply hand over the information of every child to its parent. To be
precise, let $v$ be a node that we process, and let $u$ be the node on $P$
that has $p(u)=v$. Then we set $p(v)\leftarrow u$ and
$v.\mathit{edge}\leftarrow u.\mathit{edge}$.

(c) Analysis

For convenience in the time analysis, we may use a simple implementation for
the DSU data structure which performs all unions in $O(n\log n)$ time and
every $\mathit{find}$ in $O(1)$ worst-case time. Now, the total time it takes
to perform any sequence of $\mathit{compressPath}$ operations is $O(n\log n)$.
This is because, every time $\mathit{compressPath}(T,x,y)$ is performed, it
takes $O(|P|)$ time to find the simple path $P$ that connects $x$ and $y$,
using $O(|P|)$ calls to the $\mathit{find}$ operation. Then we merge the nodes
of $P$ (thereby deleting them essentially), so they will not be traversed
again. Thus, the total time to find all paths, in all $\mathit{compressPath}$
calls, is $O(n)$. Therefore, the time bound for all $\mathit{compressPath}$
operations is dominated by that for performing the mergings (using the
$\mathit{union}$ operation), and thus it is $O(n\log n)$.

When we perform a $\mathit{joinTrees}$ operation on two trees, we may have to
reroot the smallest tree $T$, which means that we may have to traverse all of
its nodes. This takes $O(|T|)$ time and uses $O(|T|)$ calls to
$\mathit{find}$. However, a node can only be accessed during a rerooting (that
is, it may lie on the smallest tree) at most $O(\log n)$ times (because the
trees are subsequently joined to produce a bigger tree whose size is at least
twice that of the smallest). Thus, we need at most $O(n\log n)$ steps to
perform all rerootings, using at most $O(n\log n)$ calls to the
$\mathit{find}$ operation. Thus, the total time, for any sequence of
$\mathit{compressPath}$ and $\mathit{joinTrees}$ operations, is at most
$O(n\log n)$.

###  5.2 An implementation for cactuses

(a) Representation

In order to efficiently determine the cycle-path connecting two nodes of a
cactus, we represent the cactus as a rooted tree with “real nodes” and “cycle
nodes”. Every real node corresponds to a cactus node, and every cycle node
corresponds to a cycle. Thus, for every cactus $S$, there is a _cactus tree_
$T$ on the set of real and cycle nodes corresponding to $S$, which is formed
by adding edges corresponding to the incidence relation of the real nodes to
the cycle nodes. Specifically, there is an edge $(x,C)$ in $T$, where $x$ is a
real node and $C$ is a cycle node, if and only if the cactus node
corresponding to $x$ lies on the cactus cycle corresponding to $C$. We root
this tree on an arbitrary real node. Thus, the parent of a real node
(different from the root) is a cycle node, and the parent of a cycle node is a
real node. The parent of a (real or cycle) node $v$ is denoted as $p(v)$. We
use a DSU data structure to perform mergings of real nodes. This data
structure supports $\mathit{find}(x)$ and $\mathit{unite}(x,y)$, Thus, in
order to access the parent of a cycle node $C$, we use $\mathit{find}(p(C))$.

In order to retrieve the information associated with the cactus edges and to
efficiently perform the “cycle-squeezing” operation, we use doubly-linked
circular lists to represent the cycles of the cactuses. Specifically, for
every cycle $C$ of a cactus, there is a doubly-linked circular list $L$
consisting of as many nodes as there are in $C$. The nodes of $L$ correspond
to the nodes of $C$ and are ordered accordingly. Every node $x$ of $L$ has
pointers $x.\mathit{left}$ and $x.\mathit{right}$ to its neighboring nodes,
and pointers $x.\mathit{leftEdge}$ and $x.\mathit{rightEdge}$ to the
respective cactus edges.

Finally, we have the following correspondence between the nodes of the cactus
trees and the nodes of the circular lists. Let $x$ be a real node of a cactus
tree with parent $C$. Then $C$ corresponds to a cactus cycle and therefore to
a circular list $L$. Then we have a pointer for $x$ to its corresponding node
on $L$, and vice versa. Furthermore, $p(C)$ also corresponds to a node on $L$,
but we do not keep a pointer from $p(C)$ to this node (because it cannot be
uniquely determined from $p(C)$, as this can be the parent of many cycle
nodes). Instead, we have a pointer from $C$ to the node of $L$ corresponding
to $p(C)$. For notational convenience, we may use the same name to denote a
real node and its corresponding circular list node. Also, for a cycle node
$C$, we may denote the circular list node pointed to by $C$ as $p(C)$.

(b) Operations

$\mathtt{compressCyclePath}$

To perform $\mathtt{compressCyclePath(S,x,y)}$ we work as follows. First, we
determine the cycle-path $P$ connecting $x$ and $y$. To do this, we work on
the cactus tree associated with $S$; we start from $x$ and $y$, and we
alternatingly climb up the tree following the parents, marking all the nodes
that we traverse, until we meet an already marked node $z$. Then there are two
possibilities: either $(1)$ $z=x$ or $z=y$, or $(2)$ $z$ is neither $x$ nor
$y$. In the first case, assuming w.l.o.g. that $z=x$, $P$ is given by the real
nodes on the ascended path starting from $x$. In the second case, $P$ is given
by two parts: by the real nodes on the path starting from $x$ and ending in
$z$, and by the real nodes on the path starting from $y$ and ending in $z$.
(Note that $z$ can be either a cycle node or a real node.) In case $(1)$,
assuming w.l.o.g. that $z=x$, let $u_{1},C_{1},\dots,C_{k},u_{k+1}$, where
$u_{1}=x$ and $u_{k+1}=y$, be the cycle-path connecting $x$ and $y$, including
the cycles nodes that are connected with every two consecutive real nodes.
Then we only have to perform the operations
$\mathtt{squeezeCycle}(u_{i},u_{i+1},C_{i})$, for every $i\in\\{1,\dots,k\\}$,
successively. In case $(2)$, we work as in case $(1)$ for every one of the two
parts that form $P$. Furthermore, in the case that $z$ is a cycle node, we
also have to perform $\mathtt{squeezeCycle}(u,v,z)$, where $u$ and $v$ are the
second-last nodes of the two parts that form $P$. In particular, let
$u_{1},C_{1},\dots,u_{k},z$ and $v_{1},C^{\prime}_{1},\dots,v_{l},z$, where
$u_{1}=x$ and $v_{1}=y$, be the two paths that we ascended, starting from $x$
and $y$, respectively. Then, in addition to all operations
$\mathtt{squeezeCycle}(u_{i},u_{i+1},C_{i})$, for every
$i\in\\{1,\dots,k-1\\}$, and
$\mathtt{squeezeCycle}(v_{i},v_{i+1},C^{\prime}_{i})$, for every
$i\in\\{1,\dots,l-1\\}$, we also have to perform
$\mathtt{squeezeCycle}(u_{k},v_{l},z)$.

Now let us describe in detail the operation $\mathtt{squeezeCycle}(u,v,C)$,
where $u$ and $v$ are real nodes connected with a cycle node $C$.
(Intuitively, we want this operation to “squeeze” the cycle $C$ by merging its
two nodes $u$ and $v$.) We distinguish two cases, depending on whether $(i)$
$u$ and $v$ are related as ancestor and descendant, or $(ii)$ $u$ and $v$ are
siblings on the rooted cactus tree (the later occurs in case $(2)$ above, when
$z$ is a cycle node).

$(i)$ $u$ and $v$ are related as ancestor and descendant

We may assume w.l.o.g. that $v$ is an ancestor of $u$. Thus we have $p(u)=C$
and $p(C)=v$. We distinguish three cases, depending on whether $u$ has no
siblings, or $u$ is the leftmost or rightmost child of $C$ (to be defined
shortly), or neither of the previous two cases holds. First, if $u$ has no
siblings, then we simply return the two edges that connect $u$ and $v$, we
discard the cycle $C$, and we merge $u$ and $v$, setting as representative of
the union $v$. To return the two edges we use the pointer from $u$ to the node
in the circular list corresponding to $C$ (let us call it $u$ again). Then the
two edges are precisely $u.\mathit{leftEdge}$ and $u.\mathit{rightEdge}$. Now
let us consider the case that $u$ is the leftmost or rightmost child of $C$.
This is determined by checking whether $u.\mathit{left}$ or
$u.\mathit{right}$, respectively, is the node pointed to by $C$ (which
essentially corresponds to $v$). So let us assume that $u.\mathit{left}=v$
(the case that $u.\mathit{right}=v$ is treated analogously). The first thing
to do is to return the edge that connects $u$ and $v$. This is simply
$u.\mathit{leftEdge}$. Then we discard the node $u$ from the circular list and
we update it accordingly. That is, we set
$u.\mathit{right}.\mathit{left}\leftarrow v$, $v.\mathit{right}\leftarrow
u.\mathit{right}$, and $v.\mathit{rightEdge}\leftarrow u.\mathit{rightEdge}$.
Finally, we merge $u$ and $v$ (the real nodes on the cactus tree), setting as
representative of the union $v$.

Now we consider the third case. That is, we have that $u.\mathit{left}\neq v$
and $u.\mathit{right}\neq v$. (Notice that, in this case, there is no cactus
edge connecting $u$ and $v$.) Now the first thing to do is to determine the
smallest segment of the circular list $L$ corresponding to $C$ that contains
$u$ and $v$. To achieve this efficiently, we start from $u$ and $v$, and we
alternatingly follow the $\mathit{left}$ pointers, marking all the nodes that
we traverse, until we meet an already marked node $z$. Then we have that
either $z=v$ or $z=u$. Let us assume that $z=v$ (the other case is treated
analogously). Now we update the cactus tree as follows. Let $P$ be the
internal path on $L$ connecting $u$ and $v$ following the $\mathit{left}$
pointers starting from $u$ (that is,
$P=u.\mathit{left},u.\mathit{left}.\mathit{left},\dots,v.\mathit{right}$). We
introduce a new cycle node $C^{\prime}$, and we let $C^{\prime}$ be the parent
of all the real nodes that correspond to nodes of $P$. The parent of
$C^{\prime}$ is set to be $v$, and we introduce a new circular list node
$\tilde{v}$, corresponding to $v$ on the cycle $C^{\prime}$. Thus, there is a
pointer from $C^{\prime}$ to $\tilde{v}$. Now we detach $P$ from $L$ and we
attach it appropriately to the circular list corresponding to $C^{\prime}$.
This is done by setting $v.\mathit{right}.\mathit{left}\leftarrow\tilde{v}$,
$\tilde{v}.\mathit{right}\leftarrow v.\mathit{right}$,
$u.\mathit{left}.\mathit{right}\leftarrow\tilde{v}$, and
$\tilde{v}.\mathit{left}\leftarrow u.\mathit{left}$. To maintain the cactus
edges, we also set $\tilde{v}.\mathit{rightEdge}\leftarrow
v.\mathit{rightEdge}$ and $\tilde{v}.\mathit{leftEdge}\leftarrow
u.\mathit{leftEdge}$. In the list $L$ we simply discard $u$ and we update $L$
accordingly. That is, we set $u.\mathit{right}.\mathit{left}\leftarrow v$ and
$v.\mathit{right}\leftarrow u.\mathit{right}$. Again, to maintain the cactus
edge, we also set $v.\mathit{rightEdge}\leftarrow u.\mathit{rightEdge}$.
Finally, we merge $u$ and $v$ (the real nodes on the cactus tree), setting as
representative of the union $v$.

$(ii)$ $u$ and $v$ are related as siblings

Let us assume first that (the circular list nodes corresponding to) $u$ and
$v$ are neighbors. This means that either $u.\mathit{left}=v$ or
$u.\mathit{right}=v$. Suppose that $u.\mathit{left}=v$ (the other case is
treated similarly). First we return $u.\mathit{leftEdge}$: the edge that
connects $u$ and $v$. Then we discard $u$ from the circular list and we update
it accordingly. That is, we set $v.\mathit{right}\leftarrow u.\mathit{right}$,
$u.\mathit{right}.\mathit{left}\leftarrow v$, and
$v.\mathit{rightEdge}\leftarrow u.\mathit{rightEdge}$. Finally, we merge $u$
and $v$ (on the cactus tree), setting as representative of the union $v$.

Now suppose that $u$ and $v$ are not neighbors. This means that
$u.\mathit{left}\neq v$ and $u.\mathit{right}\neq v$. (Notice that, in this
case, there is no cactus edge connecting $u$ and $v$.) Let $C$ be the common
parent of $u$ and $v$, and let $w=p(C)$. Let also $L$ be the circular list
corresponding to $C$, and denote as $w$ the node of $L$ pointed to by $C$. Now
the first thing to do is to determine the smallest part of $L$ that contains
$u$ and $v$. To achieve this efficiently, we start from $u$ and $v$, and we
alternatingly follow the $\mathit{left}$ pointers, marking all the nodes that
we traverse, until we meet an already marked node $z$. Then we have that
either $z=v$ or $z=u$. Let us assume that $z=v$ (the other case is treated
analogously). Let $P$ be the internal path on $L$ connecting $u$ and $v$
following the $\mathit{left}$ pointers starting from $u$ (that is,
$P=u.\mathit{left},u.\mathit{left}.\mathit{left},\dots,v.\mathit{right}$).
Here we have that either $w\notin P$ or $w\in P$. If $w\notin P$, then we work
precisely as in the second paragraph of case $(ii)$ above. So let us assume
that $w\in P$. Then we introduce a new cycle node $C^{\prime}$, we let
$C^{\prime}$ be the parent of all the real nodes that correspond to nodes of
$P\setminus{w}$, and we let $C^{\prime}$ point to $w$. Then we introduce a new
circular list node $\tilde{v}$ (corresponding to the node that will be formed
by merging $u$ and $v$), we let $C$ point to $\tilde{v}$, and we attach the
segment $L\setminus(P\cup\\{u,v\\})$ of $L$ to $\tilde{v}$. Again, this is
done precisely as in the second paragraph of case $(ii)$ above. Furthermore,
we discard the circular list node $u$, and we properly update the list
corresponding to $C^{\prime}$. That is, we set $v.\mathit{right}\leftarrow
u.\mathit{right}$, $u.\mathit{right}.\mathit{left}\leftarrow v$, and
$v.\mathit{rightEdge}\leftarrow u.\mathit{rightEdge}$. Finally, we let the
parent of $C$ be $v$, and we merge $u$ and $v$ (the real nodes on the cactus
tree), setting as representative of the union $v$.

$\mathtt{joinCactuses}$

To perform
$\mathtt{joinCactuses(S_{1},\dots,S_{k},(x_{1},x_{2}),\dots,(x_{k},x_{1}))}$,
we first have to find the largest (w.r.t. its number of nodes) cactus among
$S_{1},\dots,S_{k}$. This can be done easily if we keep for every cactus an
attribute $\mathit{size}$, signifying its number of nodes. Now let us assume,
w.l.o.g., that one of the cactuses with the greatest size is $S_{k}$. Then we
have to do two things: to reroot the cactuses $S_{1},\dots,S_{k-1}$ on their
nodes that are to be connected on a new cycle, and then to form the cycle
$(x_{1},x_{2}),\dots,(x_{k},x_{1})$.

Let us describe how to perform a rerooting of a cactus $S$ at a node $x\in S$.
We assume that $x$ is not the root of the cactus tree of $S$ (for otherwise
there is nothing to do). First we find the path on the cactus tree that
connects $x$ with the root by following the parents. This has the form
$u_{1},C_{1},\dots,C_{t-1},u_{t}$, where $u_{1},\dots,u_{t}$ are real nodes
with $u_{1}=x$, and $C_{1},\dots,C_{t-1}$ are cycle nodes. Then we process
this path in reverse order, and for every triple $(u,C,v)$, where $u,v$ are
real nodes and $C$ is a cycle node, we do the following. (Due to reverse
processing, notice that we have $p(v)=C$ and $p(C)=u$.) Let $L$ be the
circular list corresponding to $C$. Then we simply change the pointer of $C$,
so that it points to the node of $L$ corresponding to $v$, and we reverse the
parent relation between the nodes of $(u,C,v)$. (Thus, we set $p(u)\leftarrow
C$ and $p(C)\leftarrow v$.) Finally, we update the status of $x$ so that it is
recognized as the root.

Thus we may assume that the cactus tree of every $S_{i}$,
$i\in\\{1,\dots,k-1\\}$, is rooted at $x_{i}$. Now we introduce a new cycle
node $C$, and we set the parent of every $x_{i}$, $i\in\\{1,\dots,k-1\\}$, to
be $C$, and the parent of $C$ to be $x_{k}$. Then we introduce new circular
list nodes $\tilde{x}_{1},\dots,\tilde{x}_{k}$, pointers between $x_{i}$ and
$\tilde{x}_{i}$ (in both directions), for every $i\in\\{1,\dots,k-1\\}$, and
we let $C$ point to $\tilde{x}_{k}$. All nodes $\tilde{x}_{i}$ are linked in a
circular structure according to their ordering on the new cycle. That is, we
set $\tilde{x}_{i}.\mathit{left}\leftarrow\tilde{x}_{i-1}$, for
$i\in\\{2,\dots,k\\}$, $\tilde{x}_{1}.\mathit{left}\leftarrow\tilde{x}_{k}$,
$\tilde{x}_{i}.\mathit{right}\leftarrow\tilde{x}_{i+1}$, for
$i\in\\{1,\dots,k-1\\}$, and
$\tilde{x}_{k}.\mathit{right}\leftarrow\tilde{x}_{1}$. Furthermore, we fix the
pointers to the newly introduced edges. That is, we set
$\tilde{x}_{i}.\mathit{leftEdge}\leftarrow(x_{i-1},x_{i})$, for
$i\in\\{2,\dots,k\\}$,
$\tilde{x}_{1}.\mathit{leftEdge}\leftarrow(x_{k},x_{1})$,
$\tilde{x}_{i}.\mathit{rightEdge}\leftarrow(x_{i},x_{i+1})$, for
$i\in\\{1,\dots,k-1\\}$, and
$\tilde{x}_{k}.\mathit{rightEdge}\leftarrow(x_{k},x_{1})$. Finally, we set
$S_{k}.\mathit{size}\leftarrow
S_{1}.\mathit{size}+\dots+S_{k-1}.\mathit{size}$, and the description of
$\mathtt{joinCactuses(S_{1},\dots,S_{k},(x_{1},x_{2}),\dots,(x_{k},x_{1}))}$
is complete.

(c) Analysis

First, if we use a simple implementation for the DSU data structure which
performs all unions in $O(n\log n)$ time and every $\mathit{find}$ in $O(1)$
worst-case time, we can argue as in the analysis for the data structure for
trees, that the total time it takes to find and merge all cycle-path during
any sequence of $\mathtt{compressCyclePath}$ operations is $O(n\log n)$. Thus
we only have to consider the total time it takes to perform all
$\mathtt{squeezeCycle}$ operations. Recall that $\mathtt{squeezeCycle}(u,v,C)$
has to find the smallest segment $P$ of the circular list corresponding to $C$
that contains $u$ and $v$ (all other operations of
$\mathtt{squeezeCycle}(u,v,C)$ take $O(1)$ time in total). This is performed
in $O(|P|)$ time, and then $P$ forms a new circular list on its own (plus at
most one more node). We say that the two new cycles into which $C$ was
squeezed are formed by $C$. (Thus, we may observe that after any repeated
application of $\mathtt{squeezeCycle}$ operations on $C$ and on cycles formed
by $C$, we have that all cycles formed by $C$ form a cactus.) We overload our
terminology by saying that a node of a cycle formed by $C$ is also a node of
$C$. Now we may argue as follows. Fix a cycle $C$ of size $k$ and a node $x\in
C$. Then we observe that in any sequence of $\mathtt{squeezeCycle}$ operations
on $C$ or on cycles formed by $C$, $x$ can be part of the smallest segment (on
a circular list) explored by $\mathtt{squeezeCycle}$ at most $O(\log k)$
times. Thus, the total time to perform any sequence of $\mathtt{squeezeCycle}$
operations on $C$ or on cycles formed by $C$ is $O(k\log k)$. Now observe that
the cycles are introduced into the collection of cactuses by the operation
$\mathit{joinCactuses}$; and that once a cycle has been introduced, it can
only get squeezed to form smaller cactuses. Thus, let $k_{1},\dots,k_{t}$ be
the sizes of all cycles that have been introduced in the data structure by the
operation $\mathit{joinCactuses}$. Then we have that the total time to perform
all $\mathtt{squeezeCycle}$ operations is $O(k_{1}\log k_{1}+\dots+k_{t}\log
k_{t})=O(k_{1}\log n+\dots+k_{t}\log n)=O((k_{1}+\dots+k_{t})\log n)=O(n\log
n)$, since $k_{i}=O(n)$, for every $i\in\\{1,\dots,t\\}$, and
$k_{1}+\dots+k_{t}=O(n)$.

When we perform a $\mathit{joinCactuses}$ operation on some cactuses, we may
have to reroot the smallest ones, which means that we may have to access all
of their nodes. However, we can argue as in the analysis of the data structure
for trees, in order to show that the total time-bound for all rerootings is
$O(n\log n)$. All the other operations performed in $\mathit{joinCactuses}$
take time analogous to the number of the cactuses involved. Since the total
size of all cycles that we can introduce (while maintaining a collection of
cactuses on $n$ nodes) is $O(n)$, this shows that the total time for any
sequence of $\mathit{joinCactuses}$ operations is $O(n\log n)$.

##  6 Improved data structures for trees and cactuses

Here we provide data structures and algorithms for the operations
$\mathtt{compressPath}$, $\mathtt{joinTrees}$, $\mathtt{compressCyclePath}$
and $\mathtt{joinCactuses}$, on collections of trees and cactuses with at most
$n$ nodes, with time bounds better than $O(n\log n)$. To be precise, any
sequence of $m$ operations on collections of trees or cactuses with at most
$n$ nodes can be performed in $O((n+m)\alpha(m,n))$ time in total. The
analysis for this time bound is essentially contained in [41] and [40]; our
own additions in the algorithms of [41] and [40] involve only a worst-case
$O(1)$ calls to some DSU operations and a worst-case $O(1)$ pointer
manipulations, for every operation performed. Also, the arguments that
establish correctness are sufficiently contained in the description of the
algorithms.

Now, to achieve this time bound, we will basically use the data structures
provided by La Poutré et al. [41], [40], with some minor additions to suit our
purposes. These data structures rely on the so-called “fractionally rooted
trees” (FRT), introduced in [40]. In the next section we give a brief overview
of the operations supported by FRTs. Then we describe the implementations for
collections of trees and cactuses. We only give as many details of the data
structures and algorithms of [41] and [40] as are needed in order to show
where our own additions fit in and establish our results.

###  6.1 Fractionally rooted trees

The FRT data structure operates on a forest $F$ equipped with a partition of
its edges such that the classes corresponding to this partition induce
subtrees of $F$. Before we describe the operations supported by FRT, we
introduce some terminology. We say that a node $x$ of $F$ belongs to an edge
class if it is incident to at least one edge of that class. Also, we say that
an edge class intersects a path $P$ if $P$ contains at least one edge of that
class. Now let $x,y$ be two nodes of a tree of $F$, and let $P$ be the simple
path that connects them. We call a node $z$ on $P$ a boundary node of $P$ if
it is either one of $x,y$ or it is incident to two edges of $P$ which belong
to different classes. A boundary edge set for a boundary node $z$ on $P$ is a
set of ($0$, $1$ or $2$) edges incident to $z$, one from each edge class to
which $z$ belongs and which intersects $P$. (We do not demand that the edges
in a boundary edge set for $z$ lie on $P$; however, one of their endpoints
must be $z$.) A boundary list for $P$ is a list consisting of the boundary
nodes of $P$, where each boundary node has a sublist that contains a boundary
edge set for it on $P$. Now let $L$ be a list of nodes where each node has a
sublist of edges. We say that an edge class occurs in $L$, or that $L$
contains an edge class, if there is an edge of that class in some sublist of
$L$. The edge classes of $L$ are precisely those that occur in it. A joining
list $J$ is a list of nodes with sublists of edges such that the union of the
classes occurring in $J$ induces some subtree in $F$. (We note that this is
always the case for a boundary list of a path.) In addition, the nodes in $J$
must be the nodes belonging to at least two edge classes occurring in $J$, and
the sublist for each node contains an edge for each class in $J$ to which this
node belongs. (Thus we have that a boundary list of a path is a joining list
if we remove the endpoints of the path from the list.)

Now the operations supported by FRT are the following.

  * •

$\mathtt{link}(x,y)$. Let $x,y$ be two nodes lying on different trees of $F$.
Then join the two trees by introducing a new edge $(x,y)$ in the FRT data
structure.

  * •

$\mathtt{boundary}(x,y)$. Let $x,y$ be two nodes lying on the same tree of
$F$. Then return a boundary list for the simple path with endpoints $x$ and
$y$.

  * •

$\mathtt{joinclasses}(J)$. Let $J$ be a joining list. Then join all the edge
classes of which an edge occurs in the list.

We say that a call $\mathtt{boundary}(x,y)$ is essential if there are at least
two different edge classes that intersect the simple path that connects $x$
and $y$. (Equivalently, a call $\mathtt{boundary}(x,y)$ is essential if the
boundary list that it provides contains more than two nodes.)

By [40], we have the following result.

######  Theorem 6.1.

(Theorem $9.2$ in [40]) There is an implementation of fractionally rooted
trees with the following guarantee. Suppose that we start with an empty
forest, and we perform $n$ insertions of nodes and $m$ operations
$\mathtt{link}$, $\mathtt{boundary}$, and $\mathtt{joinclasses}$, where every
essential call of $\mathtt{boundary}$ is immediately followed by
$\mathtt{joinclasses}$ on a joining list that contains all the edge classes
that occur in the list provided by $\mathtt{boundary}$. Then all these
operations can be performed in total $O((n+m)\alpha(m,n))$ time.

###  6.2 An implementation for trees

(a) Representation

For the operations $\mathtt{compressPath}$ and $\mathtt{joinTrees}$ on
collections of trees, we essentially use the solution of La Poutré for the
incremental maintenance of the $2$-edge-connected components in general graphs
with asymptotically optimal time complexity [40].

Thus we represent the collection of trees $\mathcal{C}$ as a forest $F$, which
is implemented as an FRT data structure. Every tree $T\in\mathcal{C}$
corresponds to a tree $T_{\mathit{FRT}}$ of $F$. The edges of $F$ are
partitioned into edge classes, where every edge class induces a subtree of
$F$. Some edges of $F$ are called bridges and belong to singleton classes
which are called quasi classes. All other edge classes are called real. There
is an one-to-one correspondence between the edges of a tree $T\in\mathcal{C}$
and the bridges of $T_{\mathit{FRT}}$. Thus every edge of $T_{\mathit{FRT}}$
that is a bridge contains a pointer to its corresponding edge on $T$. Every
node $x$ of $T_{\mathit{FRT}}$ belongs to at most one real class. For every
node $x$ that belongs to a real class, we maintain an edge
$x_{\mathit{assoc}}$ of that class. By shrinking the subtrees that are induced
by the real classes into single nodes, we get a natural isomorphism between
$T$ and $T_{\mathit{FRT}}$. (The idea here is that the subtrees induced by the
real classes correspond to maximal sets of nodes that got merged due to the
operation $\mathtt{compressPath}$.) Thus, every node $x\in T$ corresponds to a
subset $S$ of $T_{\mathit{FRT}}$, and we associate $x$ with a node
$x_{\mathit{FRT}}$ of $S$; conversely, every node in $S$ is associated with
$x$. To implement the later, we use a DSU data structure $\mathit{DSU}_{F}$ on
the nodes of $F$, where the representatives of the sets are nodes of the trees
of $\mathcal{C}$. $\mathit{DSU}_{F}$ supports the operations
$\mathit{find}_{F}$ and $\mathit{unite}_{F}$. Thus, in order to find which
node of $\mathcal{C}$ corresponds to a node $u$ of $F$, we use
$\mathit{find}_{F}(u)$. $\mathit{DSU}_{F}$ (and every other DSU data structure
in the sequel) is implemented using rooted trees, with path compression and
union by size, thus achieving the asymptotically optimal time complexity [52].

We can summarize the above properties as follows.

######  Property 6.2.

Let $x,y$ be two nodes of a tree $T\in\mathcal{C}$, and let $P$ be the simple
path on $T$ that connects $x$ and $y$. Let also $\tilde{P}$ be the simple path
on $T_{\mathit{FRT}}$ that connects $x_{\mathit{FRT}}$ and $y_{\mathit{FRT}}$.
Then there is an one-to-one correspondence between the edges of $P$ and the
edges of $\tilde{P}$ that are bridges. This correspondence is compatible with
that between the nodes of $T$ and the nodes of $T_{\mathit{FRT}}$. In other
words, for every bridge $(u,v)$ on $\tilde{P}$, there is an edge
$(\mathit{find}_{F}(u),\mathit{find}_{F}(v))$ on $P$.

(b) Operations

$\mathtt{compressPath}$

Let $x$ and $y$ be two distinct nodes of a tree $T\in\mathcal{C}$, and let $P$
be the simple path on $T$ that connects $x$ and $y$. To perform
$\mathit{compressPath}(T,x,y)$ we work as follows. First we call
$\mathit{boundary}(x_{\mathit{FRT}},y_{\mathit{FRT}})$ to obtain a boundary
list $L$ for the simple path $\tilde{P}$ that connects $x_{\mathit{FRT}}$ and
$y_{\mathit{FRT}}$ on $T_{\mathit{FRT}}$. According to Property 6.2, in order
to retrieve the edges of $P$, it is sufficient to identify the edges of
$\tilde{P}$ that are bridges. Since bridges belong to singleton (quasi)
classes, we have that every bridge of $\tilde{P}$ must lie in the sublist of
some node in $L$. Thus we can retrieve the bridges of $\tilde{P}$ by scanning
the sublists of $L$. (Incidentally, we note here that the efficiency of the
operation $\mathit{boundary}$ lies in the fact that it only computes boundary
nodes and corresponding edge classes, without always traversing the entire
path.) Furthermore, using again Property 6.2, we can retrieve the nodes of $P$
using the operation $\mathit{find}_{F}$ of $\mathit{DSU}_{F}$ on the endpoints
of every bridge of $\tilde{P}$.

Now, for every node $u$ in $L$ that is incident to a real class, we append
$u_{\mathit{assoc}}$ to the sublist of $u$. This is to ensure that the real
class to which $u$ belongs will get joined to all classes that occur in $L$.
(Because there is a possibility that the edge classes to which $u$ belongs and
that intersect $\tilde{P}$ are quasi classes, and so $L$ does not contain any
edge from the real edge class to which $u$ belongs.) If either
$x_{\mathit{FRT}}$ or $y_{\mathit{FRT}}$ still has only one edge in its
sublist, then it is removed from $L$. (This is to ensure that $L$ is a joining
list.) If $L$ is non-empty, then we call $\mathit{joinclasses}(L)$. Otherwise,
we have that $x_{\mathit{FRT}}$ and $y_{\mathit{FRT}}$ are connected with a
bridge $(x_{\mathit{FRT}},y_{\mathit{FRT}})$ on $T_{\mathit{FRT}}$. Then we
just change the status of $(x_{\mathit{FRT}},y_{\mathit{FRT}})$ so that it is
no longer marked as a bridge, and we convert the quasi class that contains
$(x_{\mathit{FRT}},y_{\mathit{FRT}})$ to a real class. We let the associated
edge of every node on $\tilde{P}$ be any edge on $\tilde{P}$. (For this
purpose, we may keep in a variable $e_{\mathit{temp}}$ the edge that was in
the boundary edge set of $x_{\mathit{FRT}}$ after the call
$\mathit{boundary}(x_{\mathit{FRT}},y_{\mathit{FRT}})$; so now we set
$u_{\mathit{assoc}}\leftarrow e_{\mathit{temp}}$ for every node $u$ on
$\tilde{P}$.) We introduce a new node $z$ on $T$ that replaces the entire path
$P$, and we let $z_{\mathit{FRT}}$ be any node on $\tilde{P}$. Finally, we
unite all nodes on $\tilde{P}$ using $\mathit{DSU}_{F}$, and we let $z$ be the
representative of the resulting set. This completes the description of
$\mathit{compressPath}$, which is summarized in Algorithm 4.

$P\leftarrow\emptyset$ // the set of nodes of the simple path on $T$ that
connects $x$ and $y$

$\mathcal{E}\leftarrow\emptyset$ // the set of edges of $T$ to be returned

1 $L\leftarrow\mathtt{boundary}(x_{\mathit{FRT}},y_{\mathit{FRT}})$

2 let $e_{\mathit{temp}}$ be the edge in the sublist of $x_{\mathit{FRT}}$ in
$L$

3 foreach  _node $u$ in $L$_ do

4 foreach  _edge $e$ in the sublist of $u$_ do

5 if  _$e$ is a bridge_ then

6 $\tilde{e}\leftarrow$ edge of $T$ pointed to by $e$

7 $\mathcal{E}\leftarrow\mathcal{E}\cup\\{\tilde{e}\\}$

// let $e=(z_{1},z_{2})$

8 $x_{1}\leftarrow\mathit{find}_{F}(z_{1})$

9 $x_{2}\leftarrow\mathit{find}_{F}(z_{2})$

10 $P\leftarrow P\cup\\{x_{1},x_{2}\\}$

11

12 end if

13

14 end foreach

15 if  _$u_{\mathit{assoc}}\neq\emptyset$_ then append $u_{\mathit{assoc}}$ to
the sublist of $u$

16 if  _the sublist of $u$ contains only one edge_ then remove $u$ from $L$

17

18 end foreach

19if  _$L\neq\emptyset$_ then $\mathtt{joinclasses}(L)$

20 else

21 unmark $(x_{\mathit{FRT}},y_{\mathit{FRT}})$ as a bridge

22 mark $\\{(x_{\mathit{FRT}},y_{\mathit{FRT}})\\}$ as a real class

23

24 end if

25foreach  _node $u$ in $L\cup\\{x_{\mathit{FRT}},y_{\mathit{FRT}}\\}$_ do set
$u_{\mathit{assoc}}\leftarrow e_{\mathit{temp}}$

26 let $z$ be a new node on $T$ that replaces the path $P$

27 unite all nodes in $L\cup\\{x_{\mathit{FRT}},y_{\mathit{FRT}}\\}$ using
$\mathit{DSU}_{F}$; let $z$ be the representative

28 set $z_{\mathit{FRT}}\leftarrow x_{\mathit{FRT}}$

29 return $\\{P,\mathcal{E},z\\}$

Algorithm 4 $\mathit{compressPath}(T,x,y)$

$\mathtt{joinTrees}$

Let $T_{1}$ and $T_{2}$ be two distinct trees of $\mathcal{C}$, and let $x\in
T_{1}$ and $y\in T_{2}$. Then $\mathit{joinTrees}(T_{1},T_{2},(x,y))$ is
performed by simply calling
$\mathit{link}(x_{\mathit{FRT}},y_{\mathit{FRT}})$, where
$(x_{\mathit{FRT}},y_{\mathit{FRT}})$ is marked as a bridge and the
corresponding singleton edge class is marked as a quasi class. Finally we let
$(x_{\mathit{FRT}},y_{\mathit{FRT}})$ point to $(x,y)$. (See Algorithm 5.)

1 $\mathtt{link}(x_{\mathit{FRT}},y_{\mathit{FRT}})$

2 mark $(x_{\mathit{FRT}},y_{\mathit{FRT}})$ as a bridge

3 mark $\\{(x_{\mathit{FRT}},y_{\mathit{FRT}})\\}$ as a quasi class

4 make $(x_{\mathit{FRT}},y_{\mathit{FRT}})$ point to $(x,y)$

Algorithm 5 $\mathit{joinTrees}(T_{1},T_{2},(x,y))$

###  6.3 An implementation for cactuses

(a) Representation

Following [40], we represent the cactuses with a data structure that
generalizes the concept of the tree of cycles. Recall that the tree of cycles
of a cactus is the graph that represents the incidence relation of the nodes
of the cactus to its cycles [27], [41]. By the definition of the cactus, we
have that this graph is a tree. Now we generalize the tree of cycles as
follows.

  * •

We partition the cactus $S$ into subcactuses. Based on this partition, we have
the graph $T$ that represents the incidence relation of the nodes of $S$ to
the subcactuses. (Again, we have that $T$ is a tree.)

  * •

We allow $T$ to be extended with extra nodes, that serve as copies of the
nodes of $S$. However, we demand that the resulting graph is also a tree. All
nodes of $T$ that serve as copies of the same node of $S$ are said to belong
to the same cluster. (Thus, the set of clusters is a partition of the set of
nodes of $T$ that correspond to nodes of $S$.)

We call this type of representation of a cactus $S$ a tree of cactuses. See
Figure 8 for an example of this kind of representation. (We note that,
contrary to the tree of cycles, a tree-of-cactuses representation of a cactus
is not unique.) We distinguish two types of nodes in a tree of cactuses: those
that correspond to the nodes of $S$, and they are called real nodes, and those
that correspond to the subcactuses of $S$, and they are called cactus nodes.
Thus we have a correspondence between the nodes of $S$ and the real nodes of a
tree-of-cactuses representation $T$ of $S$. Furthermore, we may speak of the
nodes of a cactus node $C$, and by that we mean the nodes of the subcactus of
$S$ that corresponds to $C$.

Figure 8: An example of a tree-of-cactuses representation of a cactus. The
square nodes are the cactus nodes. In figures A and C we can see the
corresponding subcactuses of some cactus nodes. The edges that belong to the
same edge class are painted with the same colour. The edges in black colour
constitute singleton edge classes. We can see that some real nodes correspond
to the same nodes of the cactus (and thus they belong to the same cluster).
For example, real nodes $6a$ and $6b$, in figure A, correspond to node $6$ of
the cactus. In figure B we can see an intermediate step of the call
$\mathtt{compressCyclePath}(4,10)$: this is where we have to determine the
path on the tree that connects $4$ and $10$. In figure C we can see the result