Fully Dynamic Graph Algorithms and Their Data Structures (thesis)
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.