Published on *Computer Science Department at Princeton University* (https://www.cs.princeton.edu)

Report ID:

TR-402-92

Authors:

Rauch, Monika [1]

Date:

December 1992

Pages:

121

Download Formats:

[Postscript [2]]

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.

**Links**

[1] https://www.cs.princeton.edu/research/techreps/author/172

[2] ftp://ftp.cs.princeton.edu/techreports/1992/402.ps.gz