Fully Dynamic Graph Spanners

We present fully dynamic algorithms for maintaining 3-spanners of undirected graphs under a sequence of update operations. In the case of graphs with d different edge cost values, we maintain a 3-spanner under insertion and deletion of edges; each operation is performed in O(n) amortized time over a sequence of (d · n) updates. The maintained spanner has O(d · n1.5) edges, which is known to be optimal for constant d. The same approach can be extended to graphs with real-valued edgecosts in the range [1, C]. In such case we maintain a t-spanner, with arbitrary t > 3, in O(n) amortized time per operation over a sequence of (n · logt/3 C) edge insertions and edge deletions. The maintainedspanner has O(n1.5 · logt/3 C) edges. All our algorithms are deterministic and are substantially faster thanrecomputing a spanner from scratch after each update.