Tech Report CS-92-45

Combine and Conquer

Robert F. Cohen

October 1992

Abstract:

The development of dynamic algorithms and data structures is a challenging area of research that has received much attention in the last years. For example, generalized techniques have been developed to dynamize large classes of geometric algorithms. In the area of graph algorithms such techniques are lacking. The goal of this thesis is to demonstrate generalized techniques to maintain the solutions of dynamic algorithms for graph problems, and to present dynamic algorithms based on our techniques.

We provide a framework, called {\em tree attribute system}, for maintaining the values of attributes on trees in a fully-dynamic environment. Our technique extends and generalizes the dynamic trees of Sleator and Tarjan and the decomposable search problems of Overmars. We use this technique to show two new dynamic data structures, {\em linear expression tree} and {\em linear attribute grammar}, for maintaining the solutions to tree-based expressions. These data structures are used to present fully-dynamic algorithms for a large class of problems on tree-width-two graphs, a class of graphs which include trees and series-parallel graphs. Additionally, we present a framework for the dynamic drawing of planar graphs, and demonstrate a number of fully-dynamic algorithms to draw trees, series-parallel graphs, planar $st$-graphs, and general planar graphs.

(complete text in pdf or gzipped postscript)