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 c
onnected graphs. We show an amortized lower bound of Omega(log n/k (lo
g log n + log b)) per edge insertion, deletion, or query operation in
the cell probe model, where b is the word size of the machine and ii i
s the number of vertices in G. We also show an amortized lower bound o
f Omega(log n/(log log n + log b)) per operation for fully dynamic pla
narity testing in embedded graphs. These are the first lower bounds fo
r fully dynamic connectivity problems.