Improved data structures for fully dynamic biconnectivity
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 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 general graphs and O(root n) in plane graphs for fully dynamic biconnectivity. We 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 the biconnected components of all vertices in time O(n).
data structures biconnectivity dynamic graph algorithms