@article{11681,
  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 Ω (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 Ω (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.},
  author       = {Henzinger, Monika H and Fredman, M. L.},
  issn         = {1432-0541},
  journal      = {Algorithmica},
  keywords     = {Dynamic planarity testing, Dynamic connectivity testing, Lower bounds, Cell probe model},
  number       = {3},
  pages        = {351--362},
  publisher    = {Springer Nature},
  title        = {{Lower bounds for fully dynamic connectivity problems in graphs}},
  doi          = {10.1007/pl00009228},
  volume       = {22},
  year         = {1998},
}