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: S.W. Bent, D.D. Sleator, and R.E. Tarjan, "Biased Search Trees," SIAM J. Computing t4(1985), 545- 568.
• 2: Paola Bertolazzi , Giuseppe Di Battista, On upward drawing testing of triconnected digraphs (extended abstract), Proceedings of the seventh annual symposium on Computational geometry, p.272-280, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109679]
• 3: P. Bertolazzi, G. Di Battista, R. Tamassia, and i.G. Tollis, "How to Draw a Series-Parallel Digraph," Rome, Manuscript, 1991.
• 4: Norishige Chiba , Takao Nishizeki , Shigenobu Abe , Takao Ozawa, A linear algorithm for embedding planar graphs using PQ-trees, Journal of Computer and System Sciences, v.30 n.1, p.54-76, Feb. 1985 [doi>10.1016/0022-0000(85)90004-2]
• 5: Robert F. Cohen , Roberto Tamassia, Dynamic expression trees and their applications, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.52-61, January 28-30, 1991, San Francisco, California, United States
• 6: Giuseppe Di Battista , Roberto Tamassia, Algorithms for plane representations of acyclic digraphs, Theoretical Computer Science, v.61 n.2-3, p.175-198, Nov. 1988 [doi>10.1016/0304-3975(88)90123-5]
• 7: G. Di Battista and R. Tamassia, "Incremental Planarity Testing," Proc. 30th IEEE Symp. on Foundations of Computer Science (1989), 436-441.
• 8: G. Di Battista , R. Tamassia , I. G. Tollis, Area requirement and symmetry display in drawing graphs, Proceedings of the fifth annual symposium on Computational geometry, p.51-60, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73839]
• 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: P. Eades and X. Lin, "How to Draw Directed Graphs," Proc. IEEE Workshop on VisuM Languages (VL'89) (1989), 13-17.
• 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: Herbert Edelsbrunner , Lionidas J Guibas , Jorge Stolfi, Optimal point location in a monotone subdivision, SIAM Journal on Computing, v.15 n.2, p.317-340, May 1986 [doi>10.1137/0215023]
• 13: David Eppstein , Giuseppe F. Italiano , Roberto Tamassia , Robert E. Tarjan , Jeffery Westbrook, Maintenance of a minimum spanning forest in a dynamic plane graph, Journal of Algorithms, v.13 n.1, p.33-54, March 1992 [doi>10.1016/0196-6774(92)90004-V]
• 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: H. de Fraysseix, J. Pach, and R. Pollack, "How to Draw a Planar Graph on a Grid," Combinatorica 10 (1990), 41-51.
• 16: Z. GMil, G.F. Italiano, and N. Sarnak, "Personal Communication,' 1991.
• 17: Michael T. Goodrich , Roberto Tamassia, Dynamic trees and dynamic point location, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.523-533, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103472]
• 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: Michael D. Hutton , Anna Lubiw, Upward planar drawing of single source acyclic digraphs, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.203-211, January 28-30, 1991, San Francisco, California, United States
• 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: Sven Moen, Drawing Dynamic Trees, IEEE Software, v.7 n.4, p.21-28, July 1990 [doi>10.1109/52.56447]
• 22: Joseph O'Rourke, Art gallery theorems and algorithms, Oxford University Press, Inc., New York, NY, 1987
• 23: Franco P. Preparata , Roberto Tamassia, Fully dynamic point location in a monotone subdivision, SIAM Journal on Computing, v.18 n.4, p.811-830, Aug. 1989 [doi>10.1137/0218056]
• 24: E. Reingold and J. Tilford, "Tidier Drawing of Trees," IEEE Trans. on So~~ware Engineering SE-7(1981), 223-228.
• 25: P. Rosenstiehl and R.E. Tarjan, "Rectilinear Planar Layouts of Planar Graphs and Bipolar Orientations," Discrete & Computational Geometry 1 (1986), 343- 353.
• 26: Walter Schnyder, Embedding planar graphs on the grid, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.138-148, January 22-24, 1990, San Francisco, California, United States
• 27: Daniel D. Sleator , Robert Endre Tarjan, A data structure for dynamic trees, Journal of Computer and System Sciences, v.26 n.3, p.362-391, June 1983 [doi>10.1016/0022-0000(83)90006-5]
• 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: K.J. Supowit and E.M. Reingold, "The Complexity of Drawing Trees Nicely," Acta In~ormatica 18 (1983), 377-392.
• 30: Roberto Tamassia, On embedding a graph in the grid with the minimum number of bends, SIAM Journal on Computing, v.16 n.3, p.421-444, June 1987 [doi>10.1137/0216030]
• 31: Roberto Tamassia, A Dynamic Data Structure for Planar Graph Embedding (Extended Abstract), Proceedings of the 15th International Colloquium on Automata, Languages and Programming, p.576-590, July 11-15, 1988
• 32: R. Tamassia and F.P. Preparata, "Dynamic Maintenance of Planar Digraphs, with Applications," Algorithmica 5 (1990), 509-527.
• 33: R. Tamassia and I.G. Tollis, "A Unified Approach to Visibility Representations of Planar Graphs," Discrete & ComputationM Geometry 1 (1986), 321-341.
• 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: R. Tamassia and I.G. Tollis, "Tessellation Representations of Planar Graphs," Proc. 27th Annum Allerton Conf. (1989), 48-57.
• 36: Roberto Tamassia , Ioannis G. Tollis, Representations of graphs on a cylinder, SIAM Journal on Discrete Mathematics, v.4 n.1, p.139-149, Feb. 1991 [doi>10.1137/0404014]
• 37: Roberto Tamassia , Jeffrey S. Vitter, Parallel transitive closure and point location in planar structures, SIAM Journal on Computing, v.20 n.4, p.708-725, Aug. 1991 [doi>10.1137/0220045]
• 38: C. Thomassen, "Planar Acyclic Oriented Graphs," Order 5 (1989), 349-361.
• 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: David G. Kirkpatrick , Stephen K. Wismath, Weighted Visibility Graphs of Bars and Related Flow Problems (Extended Abstract), Proceedings of the Workshop on Algorithms and Data Structures, p.325-334, August 17-19, 1989

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations; Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Theory, Verification