DYNAMIC GRAPH DRAWINGS - TREES, SERIES-PARALLEL DIGRAPHS, AND PLANAR ST-DIGRAPHS

Drawing graphs is an important problem that combines elements of compu tational geometry and graph theory. Applications can be found in a var iety of areas including circuit layout, network management, software e ngineering, and graphics. The main contributions of this paper can be summarized as follows: We devise a model for dynamic graph algorithms, based on performing queries and updates on an implicit representation of the drawing, and we show its applications. We present efficient dy namic drawing algorithms for trees and series-parallel digraphs. As fu rther applications of the model, we give dynamic drawing algorithms fo r planar st-digraphs and planar graphs. Our algorithms adopt a variety of representations (e.g., straight line, polyline, visibility) and up date the drawing in a smooth way.