BIB-VERSION:: CS-TR-v2.0
ID:: CORNELLCS//TR94-1420
ENTRY:: 1995-07-17
ORGANIZATION:: Cornell University, Computer Science Department
LANGUAGE:: English
NOTES:: Replacement. No reason was given for the revision.
TITLE:: Lower Bounds for Dynamic Connectivity Problems in Graphs
AUTHOR:: Fredman, Michael L.
AUTHOR:: Rauch, Monika H. 
DATE:: April 1994
PAGES:: 10
ABSTRACT::
We prove lower bounds on the complexity of maintaining fully dynamic $k$-edge 
or $k$-vertex connectivity in plane graphs and in $(k-1)$-vertex connected 
graphs. We show an amortized lower bound of $\Omega(\log n/k(\log\log n  + 
\log b))$ per edge insertion or deletion or per query operation in the cell 
probe model, where $b$ is the word size of the machine and $n$ is the number 
of vertices in $G$. We also show an amortized lower bound of 
$\Omega(\log n/(\log\log n  + \log b))$ per operation for fully dynamic 
planarity testing in embedded graphs. These are the first lower bounds for 
dynamic connectivity problems. 
END:: CORNELLCS//TR94-1420
BODY::
Lower Bounds for Dynamic
Connectivity Problems in Graphs
Michael L. Fredman*
Monika H= Rauch**
TR 94-1420
April 1994
Department of Computer Science
Cornell University
Ithaca, NY 14853-7501
Department of Computer Science, Rutgers University, New Brunswick, NJ 0893.
** Department of Computer Science, Cornell University, Ithaca, NY 14853.
Lower Bounds for Dynamic Connectivity Problems
in Graphs
Michael L. Eredman*
Monika H. Rauch t
Abstract
We prove lower bounds on the complexity of maintaining fully dynamic k-edge or
k-vertex connectivity in plane graphs and in (k --H 1)-veftex connected graphs. We
show an amortized lower bound of ?(log n/k (log log n + log b)) per edge insertion or
deletion or per query operation in the cell probe model, where b is the word size
of the machine and n is the number of vertices in G. We also show an amortized
lower bound of ?(log n/(log log n + log b)) per operation for fully dynamic planarity
testing in embedded graphs. These are the first lower bounds for dynamic connectivity
problems. They show that the upper bound of O(log n) or O(log2 n) for fully dynamic
connectivity, 2-connectivity, and planarity testing in plane graphs are close to optimal.
1 Introduction
This paper investigates lower bounds for dynamic data structures. Given a plane (=planar
embedded) graph G, the fully dynamic k-edge or k-vertex connectivity problem in plane
graphs is to execute the following operations in arbitrary order:
Insert(u, v) : Add the edge (u, v) to G if this does not destroy the planarity of the embed-
ding.
Delete(u, v) : Remove the edge (u, v) from G.
Query(v, v): Return yes, if u and v are k-edge or k-vertex connected, and no otherwise.
If G is not embedded, arbitrary insertions are allowed. This problem is called fully dynamic
k-edge or k-vertew connectivity problem in general graphs.
In the fully dynamic planarity testing problem in embedded graphs we execute a sequence
of edge insertions and deletions interleaved with queries of the form
Query(u, v) : Return yes, if inserting the edge (v, v) does not destroy the planarity of the
embedding, and no otherwise.
*Department of Computer Science, Rutgers University, New Brunswick, NJ 08903
tDepartment of Computer Science, Cornell University, Ithaca, NY 14853, USA. Ernail:rnhr?cs.cornell.edu
in arbitrary order. If G is not embedded, all edge insertions are allowed and the problem is
called fully dynamic planarity testing problem in general graphs.
The current best algoritlims in plane graphs take time O(log n) [1] per operation for
connectivity [1], and O(log2 n) for 2-edge-connectivity [8], 2-vertex-connectivity [9], and pla-
narity testing [7]. In planar graphs connectivity and 2-edge connectivity can be maintained
in time O(log n) per insertion and O(lo? n) per deletion [3]. The dynamic 2-vertex, 3-edge,
3-vertex, and 4-edge connectivity and planarity testing problem can be solved in planar
graphs in time O(7n) [3].
In general graphs the best upper bounds are O(7n) per operation for the dynamic
connectivity and 2-edge-connectivity problem [2] and min(?log n, n) per operation for
the 2-vertex connectivity problem [9].
In this paper we establish a lower bound on the time per operation for fully-dynamic
planarity testing of embedded graphs with n vertices, in the cell probe model with wordsize b.
In the cell probe model of computation [12], the time complexity of a sequential computation
is defined to be the number of accessed memory words. Any other operations are free. This
model is powerful enough to express all algorithms for random access machines. We show
that each operation takes amortized time ?(log n/(log log n + log b)), where n is the number
of vertices in the graph. We also describe a similar construction providing lower bounds of
?(log n/k(log log n + log b)) on the amortized time per operation for fully dynamic k-edge
connectivity and fully dynamic k-vertex connectivity in plane graphs. This shows that the
above upper bounds in plane graphs are close to optimal. The lower bounds also apply
to (k-1)-vertex connected graphs (and thus also to (k-1)-edge connected graphs), i.e. the
"hardness" of the k-edge connectivity problem does not depend on the "hardness" of the (k-
1)-edge connectivity problem. No k-edge or k-vertex connected graph with k > 3 is plane,
but we can show that the lower bounds hold in c-vertex connected plane graphs where
c = min(3, k --H 1). An earlier version of this work has appeared in [9].
We review next some related work. Westbrook and Tarjan [11] gave a lower bound for
maintaining the connected components of a graph under a sequence of edge insertions and
backtracking edge deletions. They proved that in the separable pointer machine model for
any n and any m there exists a sequence of m operations whose cost is ?(m log n/ log log n).
Fredman and Saks [6] gave a lower bound for the modular prefix sum problem in the
cell probe model of computation. The modular prefix sum problem is defined as follows:
Given an array A[1],... ,A[n] of integers mod k with initial value zero execute the following
operations in arbitrary order:
Add(l): Increase A[l] by 1.
Sum(l): Return S1 mod k, where S1 = ??i=1 A[i].
Given an algorithm in the cell probe model the proof shows that there exists a sequence of
m operations such that the algorithm takes time ?(m log n/(log log n + log b)). The lower
bound holds for arbitrary values of k. We make in the following section use of the lower
bound for the case k = 2. We call this the parity prefix sum problem.
2
2 The Lower Bounds
To show the lower bound for the dynamic connectivity and planarity testing problems we
reduce the parity prefix sum problem to them. In Section 2.1 we describe this reduction for
the planarity testing problem and in Section 2.2 we describe it for fully-dynamic k-edge and
k-vertex connectivity.
2.1 A lower bound for fully dynamic planarity testing
We are given an instance of the parity prefix sum problem, i.e. an array A of integers mod 2
and we want to solve it using an algorithm for fully-dynamic planarity testing. To represent
A we construct the following graph with n + 3 vertices which are labeled with consecutive
numbers starting with 0.
o+ Vertex i represents S? for 1 < ? < n.
o+ Vertices 0, n + 1, and n + 2 form a triangle whose face is not incident to any of the
other vertices.
o+ All vertices i with odd Si are connected by a chain (called odd cha?n) in the following
way. If Sj is odd and i is the largest index smaller than 1 such that S? is odd, there is
an edge between vertex i and vertex 1. All vertices with even S? are connected in the
same way.
o+ The first vertex feven of the even chain and the first vertex f0?? of the odd chain are
connected by an edge to vertex 0. The clockwise order of the edges at vertex 0 is as
follows: (0, n + 2), (0, n + 1), (0, feven), (0, fodd).
The last vertex 1even of the even chain and the last vertex 1odd of the odd chain are
connected to vertex n + 1 by an edge. The clockwise order at vertex n +1 is (n + 1, todd),
(n + 1, leven), (n + 1,0), and (n + 1, n + 2).
There is an edge between vertex 1oaa and vertex n +2 such that the order of the edges
at n+2is (n+2,10?), (n+2,n+1), (n+2,0). Let i be the predecessorof1o??. Then
n + 1), (1o?, n + 2), and (lo&t, i) is the order of the vertices at 1?d
For an example see Figure 1.
The odd chain, along with the edges (fodd, 0), (0, n + 1), and (n + 1, todd) forms a cycle of
edges. All vertices on the even chain are inside this cycle, but vertex n + 2 is outside. Thus
adding an edge between a vertex on the even chain and vertex n + 2 destroys the planarity
of the graph, while adding an edge between an vertex on the odd chain and vertex n + 2
preserves planarity. Hence, an edge between vertex 1 and vertex n + 2 can be added to the
graph if and only if Si is odd. This implies that a Sum(1) query can be answered by testing
whether an edge between vertex n + 2 and vertex 1 preserves the planarity of the graph.
3
13
I			0
11			12
1			2			3			4			5			6			7			8			9			10
8			3			2			4			0			6			7			2			1			3			4
Figure 1: The plane graph for the array 8 3 2 4 0 6 7 2 1 3 4.
An Add(1) changes S? for all j > 1 from odd to even and vice versa. To update the graph
appwpriately we have to cut the edge (i0?, jodd) of the odd chain with i0? < 1 and j0?? > 1
and the edge (ieven, jeven) of the even chain with ?even < 1 and ?even > 1. We describe below
how to find ?0&t, j0dd, ?even, and ?even Then we insert an edge connecting the first part of the
odd chain with the second part of the even chain and vice versa. Thus, only a constant
number of edge insertions and deletions are necessary.
To maintain the planarity of the embedding (and also the connectedness of the graph)
during these steps we maintain pointers to 1odd and teven and execute these steps in this order.
1. Delete the edges (i??,j0?) and (lodd,fl + 2).
2. Insert the edge (ieven,jo?) (such that it is consistent with the embedding).
3. Delete the edges (1??, n + 1) and (ieven,jeven).
4. Replace l?,?? by 1?? and vice versa.
5. Insert the edges (iodd,jeven), (10dd,n + 1) and (lodd,fl + 2) (in the right order of the
embedding at the vertices 1o?, n + 1, and n + 2).
To find the vertices ?odd, Jodd, ?even, and ?even we use a Van-Emde-Boas priority queue [10]
for finding predecessors in integer sets. Given the universe [0, 1,... , ?1 and a subset S of the
universe this data structure allows us to execute the following operation in arbitrary order:
Insert(x): Insert x into s, if x ?
Delete(x): Delete x from s, if x ?
Pred(x): Find the largest y ? S such that y < x, or indicate that no such element exists.
Succ(x): Find the smallest y E S such that y > x, or indicate that no such element exists.
4
Each of these operations can be executed in time O(log log n) in the cell probe model [1Oj.
In the following we denote by pred(x) (resp. succ(x)) the vertex returned by the call pred(x)
(resp. suc?x)). Note that x E 5 implies that succ(x) = pred(x) =
We store 1, n+ 1, and all indices i such that 5i-i + S? is odd in a Van-Emde-Boas priority
queue. The value 1 is inserted to guarantee that pred(l) --H 1 > 0 for all 1. The value n + 1
is inserted to guarantee that succ(l + 1) < n + 1. The priority queue can be updated with a
constant number of insert and delete operations after each Add(l) operation.
The following lemma describes how to find the edges that have to be cut.
Lemma 2.1 LetS be the value of Si before andAdd(l) operation. If(i??t,j0aa) and (ieven,jeven)
are the edges that have to be deleted after the Add(l) operation and (l',l) with 1' < 1 is the
edge on the (odd or even) chain containing 1, then
o+ Ze,,en = pred(l) --H 1 and ?even = succ(l + 1) and ?odd = 1' and ?odd = 1 if 5 is odd, and
o+ ?even = 1' and ?even = 1 and i0dd = pred(l) --H 1 and j0dd = succ(l + 1) if 5 is even.
Proof: If 5 is odd, the edge (1', 1) is the edge of the odd chain that has to be deleted.
This shows that iodd = 1' and ?odd = 1. To show that ?even = pred(l) --H 1 note that
pred(l) is the largest vertex < 1 such that S?ed(?) is odd and Spred(!)--H1 is even. Thus,
pred(l) --H 1 is the largest vertex smaller than 1 that lies on the even chain, and hence
?even = pred(l) --H 1. To show that ?even = succ(l+ 1) note that succ(l+ 1) is the smallest
vertex > 1 + 1 such that Ssncc(i+1) is even and 5s?c(1+1)--H1 is odd. Thus, succ(l) is the
smallest vertex larger than 1 that lies on the even chain, and hence ?e?en = succ(l + 1).
The proof is symmetric if 5 is even. I
If we execute an Add(4) operation in the example of Figure 1, then (3,4) and (1, 7) are the
edges to be deleted. In the example of Figure 1 the edges (3,7) and (1,4) have to be added.
See the result in Figure 2.
13
I			0			1			2			3			4			5			6			7			8			9			10			11			12
A[I]			8			3			2			5			0			6			7			2			1			3			4
Figure 2: The plane graph of the array 8 3 2 5 0 6 7 2 1 3 4.
Fredman and Saks [6] show that for any algorithm for the parity prefix sum problem there
exists a sequence of ni. operations such that the algorithm takes time ?(m log n/(log log n +
5
log b)) in the cell probe model. In the algorithm presented above this sequence uses 0(m)
edge insertions, edge deletions, and planarity queries in the plane graph and 0(m) operations
in the Van-Emde-Boas priority queue. Since each operation in the Van-Emde-Boas priority
queue takes time O(log log n) in the cell probe model, it follows that the sequence of 0(m)
edge insertions, edge deletions, and planarity queries takes time ?(mlog n/(loglog n+logb)).
This establishes the following bound.
Theorem 2.2 Any fully-dynamic planarity testing algorithm for an embedded graph requires
?(log n/(log log n + log b)) amortized time per operation in the cell probe model where b is
the number of bits in a word.
2.2 The lower bounds for fully dynamic connectivity problems
We first show the lower bounds for fully dynamic connectivity problems in k --H i-connected
graphs and then in plane graphs.
Theorem 2.3 In the cell probe model any algorithm for maintaining k-edge or k-vertex
connectivity in a (k-1)-vertex connected graph under a sequence of insertions and deletions
of edges requires ?(log n/(k log log n + log b)) amortized time per operation.
Proof: Let S0 be 1. Given a parity prefix sum problem, we construct a graph
consisting of k(n +1) vertices, labeled qp with 0 < q ? n and 1 < p < k. For a fixed q
the vertices qp are connected by a complete graph Kk. The vertices qp represent the
sum Sq. If Sq is odd and q, is the largest index smaller than q such that Sqi is odd,
there is an edge (q,p, qp) for all p. This creates k odd chains. The vertices representing
even 5q are connected in the same way and create k even chains.
Let fodd be the lowest index i larger than 0 such that Si is odd and let feien be the
lowest index i such that S? is even. If k > 1, there is an edge (fevenp, Op) for 1 < p < k.
Note that the resulting graph is (k-1)-vertex connected. In the example of Figure 3
feven = 3 and fodd = 1
Vertex 11 and vertex Ol are k-edge and k-vertex connected if and only if Si is odd.
Thus a Sum(l) operation corresponds to one k-edge or k-vertex connectivity query in
the graph.
Each Add(l) operation corresponds to the following at most k + 1 insertions and
deletions of edges in the graph. Let ?odd be the largest vertex on the odd chain that is
smaller than 1 and let j0? be the smallest vertex on the odd chain > 1. Let ?even and
?even be defined accordingly. To find ?even and ?even we maintain 1, n, and all indices
i such that 5i-i + S? is odd in a Van-Emde-Boas priority queue.
To update the graph insert the edges (i??q, jevenq) and (ievenq, jo??q) for 1 < q < k.
If i0dd = 0 or ?even = 0, then the first elements of the even and odd chains changes.
We update the pointers to feven and fodd, insert (fevenk, 0k), and delete (foddk, 0k).
6
3
1			0			1			2			4			5			6
A[1]			3			2			5			1			7			6
Figure 3: The graph constructed for the array 3 2 5 1 7 6 to show a lower bound for 3-vertex
and 3-edge connectivity in a 2-vertex connected graph.
Afterwards delete the edges (io??q, jo??q) and (i????q, jei,enq) Since the graph is (k-
1)-vertex connected before and after the update and we first insert and afterwards
deleted edges, the graph remains (k-1)-vertex connected during all insertions and
deletions.
Thus, this reduces the prefix sum problem to a fully dynamic k-edge or k-vertex
connectivity problem in a (k-1)-vertex connected graph. A sequence of m Add and
Sum operations corresponds to O(km) edge insertions, deletions, and connectivity
queries and 0(m) operations in the Van-Emde-Boas priority queue. Thus, the lower
bound for the prefix sum problem gives an amortized lower of ?(log n/(k(log log n +
log b)) per operation. I
Theorem 2.4 In the cell probe model any algorithm for maintaining k-edge or k-veflex
connectivity in a plane c-vertex connected graph under a sequence of insertions and deletions
of edges requires ?(logn/k(loglogn+logb)) amortized time per operation, where c = min(k--H
1,3).
Proof: Let S0 be 1. Given a parity prefix sum problem we construct a graph of
k(n + 2) vertices, labeled qp with 0 < q < n + 1 and 1 < p < k. There is an edge
(qp, q(p + 1)) for all q and 1 < p ? k. All vertices qp represent Sq for 0 < q < n.
If Sq is odd and q' is the largest index smaller than q such that Sqi is odd, there is
an edge (q,p, qp) for all p. This creates k odd chains. All vertices with even 5q are
connected in the same way, creating k even chains. There are no edges incident to
vertices (n + l)p, except during a Snm(l) operation.
Let fodd (feven) be the lowest index i larger than 0 such that Si is odd (even) and let
loaa (leven) be the highest index i smaller than n + 1 such that 5, is odd (even). We
maintain pointers to these 4 vertices. There is an edge (o(k + 1 --H p), fevenp) for all
1 <p < k. The embedding of the edges at qp is (qp, q(p --H 1)), (qp, q"p), (qp, q(p + 1)),
and (qp, q,p), where qip is the ancestor and q,'p is the descendant of qp in the chain
7
I			0			1			2			4			5			6			7
A[I]			3			2			5			1			7			6
Figure 4: The plane 3-vertex connected graph constructed for the array 3 2 5 1 7 6 to show
a lower bound for 4-edge and 4-vertex connectivity.
containing qp if q > 0 and q, = fodd and q" = feven if q = 0. Note that this gives a
plane graph. Figure 4 gives an example.
We maintain 1, n, and all indices i such that S2 + Sj?1 is odd in a Van-Emde-Boas
priority queue.
To answer a Stm(1) query, we add for every p the edge (loddP, (n + 1)(k + 1 --H
and (levenp, (n + l)p). This guarantees that the graph stays c-vertex connected. Then
we remove the edges (ip, t'p) with 1' > 1 and insert (ip, 11) for p> 2. Now Sum(1) is 1
if and only if vertex 11 and vertex Ol are k-vertex (or k-edge) connected. Afterwards
the original graph is restored. Thus each Sum(1) query requires 0(k) edge insertions
and deletions and one connectivity query in the graph.
An Add(t) operation changes Sj for j > 1 from even to odd and vice versa. Let
(i0aap, j0??p) for all p be the edges of the odd chains that have to be deleted, and
let (ievenp, jevenp) be the edges on the even chain. These edges can be found in time
O(log log n) using the Van-Emde-Boas priority queue as shown in lemma 2.1. To
maintain a plane c-connected graph we update the graph with the following steps:
1. Insert the edge (fevenk,01).
2. If ?o&t > 0, then execute the following steps in increasing order of p: Insert
(ievenp, joddP) and (?oddP, jevenp) (consistent with the embedding) and afterwards
delete (i0?p, joddP) and (ievenp, jevenp)
If i0?? = 0, then execute the following steps in increasing order of p: Insert
(ievenp, Op) and (i<>??p, O(k + 1 --H p)) (consistent with the embedding) and after-
wards delete (?oddP, Op) and (ievenp, O(k + 1 --H
3. Update feven, fodd, 1even, and 1odd
4. Delete (fevenk,O1).
8
As in the previous proofs, m Add and Sum operations correspond to O(km) opera-
tions in the dynamic data structure and also 0(m) operations in the Van-Emde-Boas
priority queue which implies the lower bound. I
References
[1]
D. Eppstein, G. F. Italiano, R. Tamassia, R. E. Tarjan, J. Westbrook, M. Yung, "Main-
tenance of a Minimum Spanning Forest in a Dynamic Planar Graph" J.Algorithms, 13
(1992), 33--H54.
[2] D. Eppstein, Z. Galil, G. F. Italiano, A. Nissenzweig, "Sparsification - A technique for
speeding up dynamic graph algorithms" Proc. 33nd Annual IFEE Symp. on Foundations
of Computer Science, 1992.
[3] D. Eppstein, Z. Galil, G. F. Italiano, T. H. Spencer, "Separator Based Sparsification
for Dynamic Planar Graph Algorithms" Proc. 23nd Annual ACM Symp. on Theory of
Computing, 1993.
[4] G. N. Prederickson, "Data Structures for On-line Updating of Minimum Spanning Trees"
SlAM J. Comput. 14 (1985), 781--H798.
[5] G. N. Frederickson, "Ambivalent Data Structures for Dynamic 2-edge-connectivity and
k smallest spanning trees" Proc. 32nd Annual IEEE Symp. on Foundation of Comput.
Sci., 1991, 632--H641.
[6] M. L. Fredman, and M. E. Saks, "The Cell Probe Complexity of Dynamic Data Struc-
tures", Proc. 19th Annual Symp. on Theory of Computing, 1989, 345--H354.
[7]
G. Italiano, H. La Poutre', and M. Rauch, "Fully Dynamic Planarity Testing in Embedded
Graphs" in: T. Lengauer (Ed.), Algorithms - ESA `93' LNCS 726, Springer Verlag, 1993,
pages 212-223.
[8] J. Hershberger, M. Rauch, 5. Suri, "Fully Dynamic 2--HEdge--HConnectivity in Planar
Graphs" Proc. 3rd Scandinavian Workshop on Algorithm Theory, LNCS 621, Springer-
Verlag, 1992, 233--H244.
[9j M. II. Rauch. "Improved Data Structures for Fully Dynamic Biconnectivity" to appear
in Proc. 26th Annual Symp. on Theory of Computing 1994.
[10] P. van Emde Boas, "Preserving order in a forest in less than logarithmic time and linear
space", Inform. Process. Lett., 6(3), 1977, 80--H82.
[11] R. E. Tarjan, J. Westbrook, "Amortized Analysis of Algorithms for Set Union with
Backtracking", SlAM J. Comput., 18(1), 1989, 1--H11. biconnected components on-line"
Algorithmica 7 (1992), 433--H464.
9
[12] A. Yao, "Sliould tables be sorted", J. Assoc. Comput. Mach., 28(3), 1981, 615--H628.
10
