The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 24 NO.5 / (1995))
Dynamic Graph Drawings: Trees, Series-Parallel Digraphs, and Planar ST-Digraphs
Robert F. Cohen, Giuseppe Di Battista, Roberto Tamassia, Ioannis G. Tollis,
Pages. 970-1001
Abstract 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,\indent The main contributions of this paper can be summarized as follows:\indent $ullet$ 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.\indent $ullet$ We present efficient dynamic drawing algorithms for threes and series-parallel
digraphs.\indent 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.
Contents 1. Introduction
1.1. Definitions
1.2. Model
1.3. Overview
2. Dynamic tree drawing
2.1. $\Box$-drawings
2.2. Dynamic environment
2.3. Data structure
2.4. Query operations
3. Series parallel digraphs
3.1. $\Delta$-drawings
3.2. Dynamic environment
3.3. Data structure
3.4. Qury operations
3.5. Update operations
4. Planar graphs
4.1. Upward drawings
4.2. Visibility drawings
4.3. Biconnected planar graphs
5. Open problems
Key words graph drawing, dynamic algorithms, data structures, layout, trees, series-parallel digraphs, planar graphs.
Mathmatical Subject Classification 68Q20, 68Q05, 05C85, 65Y25