Experimental Evaluation of Algorithms for Incremental Graph
Connectivity and Biconnectivity

Madhukar Korupolu, Ramgopal R. Mettu, Vijaya Ramachandran, and Yuke Zhao

We consider an algorithm to maintain the connected components and the
biconnected components of a graph where vertex and edge insertions are
allowed.  Algorithms for this problem can be applied to task
decomposition in engineering design.  Connected components are
maintained using a disjoint set data structure and the biconnected
components are maintained by a block forest.  We develop a special
disjoint set structure that allows selective deletion of the elements,
and enables us to create and use \emph{condensible nodes}.  The
algorithm runs in $O((n\log n)+ m)$ time, where $n$ is the number of
vertices and $m$ is the number of operations.  Finally, we present
extensive timing information for out implementation.