A framework for dynamic graph drawing

ABSTRACT

In this paper we give a model for dynamic graph algorithms, based on performing queries and updates on an implicit representation of the drawing. We present dynamic algorithms for drawing planar graphs that use a variety of drawing standards (such as polyline, straight-line, orthogonal, grid, upward, and visibility drawings), and address aesthetic criteria that are important for readability, such as the display of planarity, symmetry, and reachability. Also, we provide techniques that are especially tailored for important subclasses of planar graphs such as trees and series-parallel digraphs. Our dynamic drawing algorithms have the important property of performing “smooth updates” of the drawing. Of special geometric interest is the possibility of performing point-location and window queries on the implicit representation of the drawing.

References

1. 1.S.W. Bent, D.D. Sleator, and R.E. Tarjan, "Biased Search Trees," SIAM J. Computing t4(1985), 545- 568.
2. 2.P. Bertolazzi and G. Di Battista, "On Upward Drawing Testing of Triconnected Digraphs," Proc. A CM Syrup. on Computational Geometry (1991).
3. 3.P. Bertolazzi, G. Di Battista, R. Tamassia, and i.G. Tollis, "How to Draw a Series-Parallel Digraph," Rome, Manuscript, 1991.
4. 4.N. Chiba, T. Nishizeki, S. Abe, and T. Ozawa, "A Linear Algorithm for Embedding Planar Graphs Using PQ-Trees," J. of Computer and System Sciences 30 (1985), 54-76.
5. 5.R.F. Cohen and R. Tamassia, "Dynamic Expression Trees and their Apphcations," Proc. A CM-SIAM Syrup. on Discrete Algorithms (1991), 52-61.
6. 6.G. Di Battista and R. Tamassia, "Algorithms for Plane Representations of Acyclic Digraphs," TheoreticM Computer Science 61 (1988), 175-198.
7. 7.G. Di Battista and R. Tamassia, "Incremental Planarity Testing," Proc. 30th IEEE Symp. on Foundations of Computer Science (1989), 436-441.
8. 8.G. Di Battista, R. Tamassia, and I.G. Tollis, "Area Requirement and Symmetry Display in Drawing Graphs," Proc. A CM Syrup. on ComputationM Geometry (1989), 51-60.
9. 9.D. Dolev, F.T. Leighton, and H. Trickey, "Planar Embedding of Planar Graphs," in Advances in Comput- ~ng Research, vol. 2, F.P. Preparata, ed., JAI Press Inc., Greenwich, CT, 1984, 147-161.
10. 10.P. Eades and X. Lin, "How to Draw Directed Graphs," Proc. IEEE Workshop on VisuM Languages (VL'89) (1989), 13-17.
11. 11.P. Eades and R. Tamassia, "Algorithms for Automatic Graph Drawing: An Annotated Bibhography," Dept. of Computer Science, Brown Univ., Technical Report CS-89-09, 1989.
12. 12.H. Edelsbrunner, L.J. Guibas, and J. Stolfi, "Optimal Point Location in a Monotone Subdivision," SIAM J. Computing 15 (1986), 317-340.
13. 13.D. Eppstein, G.F. ItaJiano, R. Tamassia, R.E. Tarjan, J. Westbrook, and M. Yung, "Maintenance of a Minimum Spanning Forest in a Dynamic Plane Graph," J. of Algorithms 13 (1992), 33-54.
14. 14.M. Formann, T. Hagerup, J. Haralambides, M. Kaufmann, F.T. Leighton, A. Simvonis, E. Welzl, and G. Woeginger, "Drawing Graphs in the Plane with High Resolution," Proc. IEEE Syrup. on Foundations of Computer Science (1990), 86-95.
15. 15.H. de Fraysseix, J. Pach, and R. Pollack, "How to Draw a Planar Graph on a Grid," Combinatorica 10 (1990), 41-51.
16. 16.Z. GMil, G.F. Italiano, and N. Sarnak, "Personal Communication,' 1991.
17. 17.M.T. Goodrich and R. Tamassia, "Dynamic Trees and Dynamic Point Location," Proc. 23th ACM Syrup. on Theory of Computing (1991), 523-533.
18. 18.L.J. Guibas and F.F. Yao, "On Translating a Set of Rectangles," in Advances in Computing Research, vol. 1, F.P. Preparata, ed., JAI Press Inc., Greenwich, CT, 1983, 61-77.
19. 19.M.D. Hutton and A. Lubiw, "Upward Planar Drawing of Single Source Acyclic Digraphs," Proc. A CM-SIAM Syrup. on Discrete Algorithms (1991), 203-211.
20. 20.A. Lempel, S. Even, and I. Cederbaum, "An Algorithm for Planarity Testing of Graphs," in Theory of Graphs, Int. Symposium (Rome, 1966), Gordon and Breach, New York, 1967, 215-232.
21. 21.S. Moen, "Drawing Dynamic Trees," IEEE Software 7 (1990), 21-28.
22. 22.J. O'Rourke, Art Gallery Theorems and Algorithms, Oxford University Press, 1987.
23. 23.F.P. Preparata and R. Tamassia, "Fully Dynamic Point Location in a Monotone Subdivision," SIAM J. Computing 18 (1989), 811-830.
24. 24.E. Reingold and J. Tilford, "Tidier Drawing of Trees," IEEE Trans. on So~~ware Engineering SE-7(1981), 223-228.
25. 25.P. Rosenstiehl and R.E. Tarjan, "Rectilinear Planar Layouts of Planar Graphs and Bipolar Orientations," Discrete & Computational Geometry 1 (1986), 343- 353.
26. 26.W. Schnyder, "Embedding Planar Graphs on the Grid," Proc. ACM-SIAM Syrup. on Discrete Algorithms (1990), 138-148.
27. 27.D.D. Sleator and R.E. Tarjan, "A Data Structure for Dynamic Trees," J. Computer Systems Sciences 24 (1983), 362-381.
28. 28.K. Sugiyama, S. Tagawa, and M. Toda, "Methods for Visual Understanding of Hierarchical Systems," IEEE Trans. on Systems, Man, and Cybernetics SMC-11 (1981), 109-125.
29. 29.K.J. Supowit and E.M. Reingold, "The Complexity of Drawing Trees Nicely," Acta In~ormatica 18 (1983), 377-392.
30. 30.R. Tamassia, "On Embedding a Graph in the Grid with the Minimum Number of Bends," SIAM J. Computing 16 (1987), 421-444.
31. 31.R. Tamassia, "A Dynamic Data Structure for Planar Graph Embedding," Proc. 15th ICALP, LNCS 317 (t 988), ,576-590.
32. 32.R. Tamassia and F.P. Preparata, "Dynamic Maintenance of Planar Digraphs, with Applications," Algorithmica 5 (1990), 509-527.
33. 33.R. Tamassia and I.G. Tollis, "A Unified Approach to Visibility Representations of Planar Graphs," Discrete & ComputationM Geometry 1 (1986), 321-341.
34. 34.R. Tamassia and I.G. Tollis, "Planar Grid Embedding in Linear Time," IEEE Trans. on Circuits and Systems CAS-36 (1989), 1230-1234.
35. 35.R. Tamassia and I.G. Tollis, "Tessellation Representations of Planar Graphs," Proc. 27th Annum Allerton Conf. (1989), 48-57.
36. 36.R. Tamassia and I.G. Tollis, "Representations of Graphs on a Cylinder," ,9IAM J. on Discrete Mathematics 4 (1991), 139-149.
37. 37.R. Tamassia and J.S. Vitter, "Parallel Transitive Closure and Point Location in Planar Structures," SIAM J. Computing 20(1991), 708-725.
38. 38.C. Thomassen, "Planar Acyclic Oriented Graphs," Order 5 (1989), 349-361.
39. 39.J. Valdes, R.E. Tarjan, and E.L. Lawler, "The Recognition of Series Parallel Digraphs," SIAM J. on Computing 11 (1982), 298-ala.
40. 40.S.K. Wismath, "Weighted Visibility Graphs of Bars and Related Flow Problems," Algorithms and Data Structures (Proc. WADS'89)(1989), 325-334.

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Graph algorithms

      • Trees

• Theory of computation

  • Randomness, geometry and discrete structures

    • Computational geometry