Lower bounds for fully dynamic connectivity problems in graphs

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 _0_(log n/k(log 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 n is the number of vertices in G. We also show an amortized lower bound of _0_(log n/(log log n + log b)) per operation for fully dynamic planarity testing in embedded graphs. These are the first lower bounds for fully dynamic connectivity problems