Dynamic Graph Drawings: Trees, Series-Parallel Digraphs, and Planar $ST$-Digraphs
Robert F. Cohen, Giuseppe Di Battista, Roberto Tamassia, Ioannis G. Tollis · SIAM Journal on Computing · 1995
Drawing graphs is an important problem that combines elements of computational geometry and graph theory. Applications can be found in a variety of areas including circuit layout, network management, software engineering, 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 dynamic drawing algorithms for trees and series-parallel digraphs. As further applications of the model, we give dynamic drawing algorithms for planar $st$-digraphs and planar graphs. Our algorithms adopt a variety of representations (e.g., straight line, polyline, visibility) and update the drawing in a smooth way.