@article{11893,
abstract = {We present fully dynamic algorithms for maintaining the biconnected components in general and plane graphs.
A fully dynamic algorithm maintains a graph during a sequence of insertions and deletions of edges or isolated vertices. Let m be the number of edges and n be the number of vertices in a graph. The time per operation of the best deterministic algorithms is 𝑂(𝑛√) in general graphs and O(log n) in plane graphs for fully dynamic connectivity and O(min m2/3 ,n}) in general graphs and 𝑂(𝑛√) in plane graphs for fully dynamic biconnectivity. We improve the later running times to 𝑂(𝑚log𝑛‾‾‾‾‾‾‾√) in general graphs and O(log 2n ) in plane graphs. Our algorithm for general graphscan also find the biconnected components of all vertices in time O(n).},
author = {Henzinger, Monika H},
issn = {1095-7111},
journal = {SIAM Journal on Computing},
number = {6},
pages = {1761--1815},
publisher = {Society for Industrial & Applied Mathematics},
title = {{Improved data structures for fully dynamic biconnectivity}},
doi = {10.1137/s0097539794263907},
volume = {29},
year = {2000},
}