Experimental Evaluation and Comparison of Algorithms for Incremental
Graph Connectivity

Ramgopal R. Mettu, Yuke Zhao, Vijaya Ramachandran

We describe our implementation of 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
implemented an incremental biconnectivity algorithm presented in
Westbrook and Tarjan (Algorithmica (1992)7:433-464) which runs in
$O((n\log n)+m)$ time, where $n$ is the number of vertices and $m$ is
the number of operations.  However, the algorithm of Westbrook and
Tarjan does not address the issue of deletions in disjoint sets, which
seem to be needed in order to implement the algorithm correctly.
Hence we develop the concepts of \emph{dynamic holes} and \emph{static
holes} to support variations of the standard disjoint set structure
that allow the deletion of certain elements.  We present four
different implementations of the incremental biconnetivity algorithm
which utilize these variants of the standard disjoint set structure,
and analyze their performance.  We present extensive tinming
information for each of these implementations.