Fully Dynamic Graph Algorithms and Their Data Structures (thesis)
Report ID: TR-402-92Author: Rauch, Monika
Date: 1993-01-00
Pages: 121
Download Formats: |Postscript|
Abstract:
We present four fully dynamic algorithms, i.e., algorithms that are able to answer queries about properties of a graph or a set during a sequence of modifications of the graph or set. Additionally, we give lower bounds for fully dynamic graph algorithms. The first three algorithms maintain properties of graphs during insertions and deletions of edges and vertices. %These algorithms are called fully dynamic graph algorithms. Let $n$ denote the number of vertices in a graph and $m$ the number of edges. We give the first sublinear time algorithm for maintaining biconnectivity in graphs. A query can be answered in constant time. The amortized time of an insertion or deletion is $O(m^{2/3})$. A slight variation of the algorithm gives an amortized running time of $O(sqrt {n} log n)$ per insertion or deletion in a plane graph. The worst-case running time per query is $O(log ^2 n)$ in a plane graph. The second data structure maintains two-edge connectivity in plane graphs in a fully dynamic environment. It achieves a worst case running time of $O(log ^2 n)$ per insertion or deletion and $O(log n)$ per query. Finally, we give an algorithm for deciding whether adding an edge to a plane graph maintains the planarity of its embedding. If the edge can be added, the algorithm returns a face into which the edge can be embedded without destroying the planarity of the embedding. Any query and any insertion or deletion of an edge takes $O(log ^2 n)$ time. All of the algorithms use $O(n)$ space and isolated vertices may be inserted in constant time. In addition, we give a lower bound in the cell probe model of $Omega (log n / log log n)$ per operation for fully-dynamic planarity testing and for fully-dynamic $k$-edge connectivity and $k$-vertex connectivity in plane graphs for constant $k$. The fourth algorithm maintains predecessors in integer sets during insertions and deletions of elements. The integers are chosen from the universe ${0, 1, dots ,u-1}$. There is an upper bound of $O( log log u)$ for this problem and a lower bound of $Omega (log log u)$ per query operation (even for randomized algorithms) in the cell probe model. If the set of numbers is uniformly distributed over the universe, we give an algorithm with worst case query time $O(1)$ and amortized expected time $O(1)$ for any insertion or deletion.