Henzinger, Monika R.Fredman, Michael L.2007-01-182007-01-182007-01-18199810.1007/PL000092282-s2.0-0008802771https://infoscience.epfl.ch/handle/20.500.14299/239612We 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.Cell probe modelDynamic connectivity testingDynamic planarity testingLower boundstext::journal::journal article::research article