Introduction 
Traditional graph algorithms operate on static graphs. A fixed graph is given, and an algorithmic problem (e.g., "Is the graph planar?") is solved on the graph. Dynamic graphs are not fixed in time, but can evolve through local changes of the graph. The algorithmic problem has to be resolved quickly after each modification. Dynamic graphs model many graphs occurring in reallife applications much more closely, because no large system is truly static. In network routing, for instance, a communications network changes as nodes and links go down and up due to failures and repairs. A dynamic graph algorithm is a data structure operating on a graph supporting two types of operations: updates and queries. An update is a local change of the graph (e.g., insertion or deletion of an edge) and a query is a question about a certain property of the current graph (e.g., "Are nodes u and v connected in the current graph?"). The aim of such a data structure is to use structural information about the current graph in order to handle an update faster than by the obvious solution, that is recomputing everything from scratch with a static algorithm. Usually, queries take less time than updates, and the sequence of operations (updates and queries) is not known in advance. LEDA is a library of data types and algorithms for combinatorial and geometrical computing in C++. In particular, LEDA contains flexible and powerful data types and a wealth of algorithms for computational problems in graph theory. However, there is yet only few support for dynamic graph algorithms. The aim of this project is to add common dynamic graph algorithms to LEDA and to enhance the support for implementing dynamic graph algorithms with LEDA. This is a LEDA Extension Package (LEP) which is shipped as an optional library with LEDA. 
State 
The second beta version of the package is available. 
People 

Contributions 

Related Papers 

The LEP Dynamic Graphs Group , 6 Jul 1998