Improved data structures for fully dynamic biconnectivity

We present fully dynamic algorithms for maintaining the biconnected compone nts 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 b est deterministic algorithms is O(root n) in general graphs and O(log n) in plane graphs for fully dynamic connectivity and O(min{m(2/3), n}) in gener al graphs and O(root n) in plane graphs for fully dynamic biconnectivity. W e improve the later running times to O(root m log n) in general graphs and O(log(2) n) in plane graphs. Our algorithm for general graphs can also nd t he biconnected components of all vertices in time O(n).