Dynamic Graph Algorithms

INTRODUCTION Dynamic graph algorithms are algorithms that maintain properties of a (possibly edgeweighted) graph while the graph is changing. These algorithms are potentially useful in a number of application areas, including communication networks, VLSI design, distributed computing, and graphics, where the underlying graphs are subject to dynamic changes. Efficient dynamic graph algorithms are also used as subroutines in algorithms that build and modify graphs as part of larger tasks, e.g., the algorithm for constructing Voronoi diagrams by building planar subdivisions. GLOSSARY Update: an operation that changes the graph. The primitive updates considered in the literature are edge insertions and deletions and, in the case of edge-weighted graphs, changes in edge weights. Query: a request for information about the property being maintained. For example, if the property is planarity, a query simply asks whether the graph is currentl