@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},
}

@inproceedings{4097,
  abstract     = {Arrangements of curves in the plane are of fundamental significance in many problems of computational and combinatorial geometry (e.g. motion planning, algebraic cell decomposition, etc.). In this paper we study various topological and combinatorial properties of such arrangements under some mild assumptions on the shape of the curves, and develop basic tools for the construction, manipulation, and analysis of these arrangements. Our main results include a generalization of the zone theorem of [EOS], [CGL] to arrangements of curves (in which we show that the combinatorial complexity of the zone of a curve is nearly linear in the number of curves), and an application of (some weaker variant of) that theorem to obtain a nearly quadratic incremental algorithm for the construction of such arrangements.},
  author       = {Edelsbrunner, Herbert and Guibas, Leonidas and Pach, János and Pollack, Richard and Seidel, Raimund and Sharir, Micha},
  booktitle    = {15th International Colloquium on Automata, Languages and Programming},
  isbn         = {978-3-540-19488-0},
  keywords     = {line segment, computational geometry, Jordan curve, cell decomposition, vertical tangency},
  location     = {Tampere, Finland},
  pages        = {214 -- 229},
  publisher    = {Springer},
  title        = {{Arrangements of curves in the plane - topology, combinatorics, and algorithms}},
  doi          = {10.1007/3-540-19488-6_118},
  volume       = {317},
  year         = {1988},
}