Publication
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.
Nathanaël Perraudin, Andreas Loukas, Karolis Martinkus
Karl Aberer, Thành Tâm Nguyên, Chi Thang Duong