On Dynamic Graphs (Invited Talk)

In graph algorithms, many questions about a graph can be answered in time proportional to the size of the input, and such linear time algorithms are considered the epitome of efficiency. However, when the graph changes slightly, e.g. by the insertion or deletion of an edge or a vertex, it is undesirable to consider the entire input again. Rather, one would wish to keep some of the partial answers to questions about the old graph, and re-use them when computing answers to questions about the resulting graph. The art of handling such changes is studied in dynamic graph algorithms. In this talk, we will see some examples of ideas and techniques for efficiently maintaining knowledge about a dynamically changing graph. We will consider classical and natural graph properties such as connectivity and planarity, and we will focus on deterministic algorithms.