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 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.