Dynamic Graph Layout

Abstract

Data in real world graph drawing applications often change frequently but incrementally. Any drastic change in the graph layout could disrupt a user's "mental map". Furthermore, real world applications like enterprise process or e-commerce graphing, where data increases rapidly, demand a comprehensive responsiveness when rendering the graph layout in a multi-user environment in real time. Most standard static graph drawing algorithms apply global changes and redraw the entire graph layout whenever the data changes. The new layout may be very different from the previous layout and the time taken to redraw the entire graph degrades quickly as the amount of graph data grows. Dynamic behavior and the quantity of data of real world applications pose challenges for existing graph drawing algorithms in terms of incremental stability and scalability. A constrained hierarchical graph drawing framework and modified Sugiyama heuristic are proposed in this research. The goal of this research is to improve the performance and scalability of the constrained graph drawing framework while preserving layout stability. The primary innovation of the proposed constrained hierarchical graph drawing framework is to use a relational data model to improve the performance of the algorithm by reusing vertex and edge information stored in a relational database . This research is based on the work of North and Woodhull (2001) and the constrained crossing reduction problem proposed by Forster (2004). The result of the proposed constrained hierarchical graph drawing framework and the new Sugiyama heuristic, especially the modified barycenter algorithms, will be tested and evaluated against North and Woodhull’s (2001) Online Graph Drawing Framework.

Research

Approved iea paper
Formal proposal - latest version 9.3
The proposal is being written. This page is updated frequently

Advisors

1. Dr. Laszlo, Michael (Main advisor)
2. Dr. Sun, Junping
3. Dr. Li, Wei

Sugiyama Pseudocode

• Greedy Cycle Removal pseudocode
  
• Layer Assignment pseudocode
  
• Label Vertices sub-routine pseudocode called Layer Assignment
• Find unassigned to layer vertices sub-rountine called Layer Assignment pseudocode
• Layer to Layer Sweep pseudocode
• One side two-layered crossing reduction pseudocode
• Compute barycenter for vertices pseudocode
• Froster implementation One side two-layered crossing reduction pseudocode

Demo, Snapshots, and Source Code

• Source code
  A html version of source code (being updated frequently)
• GraphViewer
  A basic graph viewer (applet) - for visualization testing purposes (still underdevelopment). [Tested under linux/firefox 3.0]
• Graph Snapshots
  These snapshots were taken from graph viewer showing the result of the graph after layer assignment algorithm is completed including adding dummy vertices to ensure the graph is propered before executing the one-side two-layered crossing heuristics.
• DDL script of the graph database
  This data contains vertices, edges and series of snapshots of graph layout.

Extended Dot Grammar

Extended dot grammar includes following functions

• Add vertices
• Add edges
• Remove vertices
• Remove edges
• Set vertice constraints
• Set order constraints

Applications

Applications of this research include but not limited to enterprise process modeling tool, online family tree (redenring large tree) etc.

References

• Battista, G. D., Eades, P., Tamassia, R., & Tollis, I. (1999). Graph drawing algorithms for the visualization of graphs. New Jersey: Prentice Hall.
• Bohringer, K., & Newbery, P. (1990). Using constraints to achieve stability in automatic graph layout algorithms. Proceedings of ACM CH 90, 43-51.
• Brandes, U., & Wagner, D. (1997). A Bayesian paradigm for dynamic graph layout. Proc. Measures for GSymp. Graph Drawing GD '97, pp. 236-247.
• Bridgeman, S., & Tamassia, R. (2002). A user study in similarity measures for graph drawing. Journal of Graph Algorithms and Applications, 6(3), 225-254.
• Buchsbaum, A. L., & Westbrook, J. R. (2000). Maintaining hierarchical graph views. Proceedings of the Eleventh Annual ACM-Siam Symposium on Discrete Algorithms. 566-575.
• Catarci, T. (1988). The assignment heuristic for crossing reduction. IEEE Trans. Syst. Man Cybern. 25(3), 515-521.
• Coffman, E. G., & Graham, R. L. (1972). Optimal scheduling for two processors systems. Acta Informica 1, pp. 200-213.
• Cohen, R. F., Battista, G. D., Tamassia, R., Tollis, I. G., & Bertolazzi, P. (1992). A framework for dynamic graph drawing. Annual Symposium on Computational Geometry: Proceedings of the Eighth Annual Symposium On Computational Geometry (pp. 261-270). Berlin: ACM.
• Demetrescu, C., & Finocchi, I. (2003). Combinatorial algorithms for feedback problems in directed graphs. Information Processing Letters, 86(3), 129-136.
• Davison, R., & Harell, D. (1996). Drawing graphs nicely using simulated annealing. ACM Transactions on Graphics Vol. 15 (301—331)
• Diehl, S., & Görg, C. (2002). Graphs, they are changing. Lecture Notes In Computer Science Vol. 2528 (23-30).
• Diehl, S., Görg, C., Kerren, A. (2000). Foresighted graph layout. Technical Report, FR Informatik, Saarland University.
• Diehl, S., Görg, C., Kerren, A. (2001). Preserving the mental map using foresighted layout. In Proceedings of the Joint Eurographics -- IEEE TCVG Symposium on Visualization. Switzerland.
• Eades, P. (2005). How to get a PhD in Information Technology. Retrieved May 02, 2007 from http://www.cs.usyd.edu.au/~peter/howtogetphdusyd.pps
• Eades, P., & Kelly, D. (1984). The Marey graph animation tool demo. Proceedings of the 8th International Symposium on Graph Drawing, 396 - 406.
• Eades, P., & Kelly, D. (1986). Heuristics for reducing crossings in 2-layered networks, Ars combin., pp. 187-191. Proceedings of the Australian Computer Science Conference, 327-334.
• Eades, P., Lin, X. Y, & Smith, W. (1993). A fast and effective heuristic for the feedback arc set problem. Information Processing Letters, 12-15.
• Eiglsperger, M., Siebenhaller, M., & Kaufmann, M. (2005). An efficient implementation of Sugiyama's algorithm for layered graph drawing. Journal of Graph Algorithms and Applications, 9(3), 305-325.
• Finocchi, I. (2002). Hierarchical decompositions for visualizing large graphs. Ph. D thesis. Università̀ degli Studi di Roma, Rome.
• Forster, M. (2004). A fast and simple heuristic for constrained two-layered crossing reduction. Proc. Graph Drawing, GD 2004, 206-216.
• Frishman, Y., & Tal, A. (2007). On-line dynamic graph drawing. Eurographic/ IEEE-VGTC Symposium on Visualization.
• Gansner, E. R., North, S. C., & Vo, K. P. (1993). A technique for drawing directed graphs. IEEE Transactions on Software Engineering, 19(3), 214-230.
• Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-complete. New York: W. H. Freeman.
• Garey, M. R., & Johnson, D. S. (1983). Crossing number is NP-complete. SIAM Journal on Algebraic and Discrete Methods, 4(3), 312-316.
• Gorg, C. (2005). Offline drawing of dynamic graphs. Ph. D Dissertation. Saarland University, Saarbrücken, Germany.
• Gorg, C., Birke, P., Pohl, M., & Diehl, S. (2004). Dynamic graph drawing of sequences of orthogonal and hierarchical graphs. Proceedings of 12th International Symposium on Graph Drawing.
• He, W., & Marriott, K. (1998). Constrained graph layout. An International Journal, 3, 289-314. Boston: Kluwer Academic Publishers.
• Huang, W., & Eades, P. (2005). How people read graphs. Asia Pacific Symposium on Information Visualization (APVIS 2005). Australia.
• Junger, M., & Mutzel, P. (1997). 2-layer straightline crossing minimization: Performance of exact and heuristic algorithms. J. Graph Algorithms and Applications, 1(1), 1-25.
• Knuth, D. E. (1996). Guest Lecture. Preceding Graph Drawing 1996.
• Lam, S., & Sethi, R. (1979). Worst case analysis of two scheduling algorithms. SIAM Journal on Computing, 6(3), 518.
• Lee, Y. Y., Lin, C. C., & Yen, H. C. (2006). Mental map preserving graph drawing using simulated annealing. Vol. 60 of Conferences in Research and Practice in Information Technology.
• Li, X. Y., & Stallmann, M. (2002). New bounds on the barycenter heuristic for bipartite graph drawing. Information Processing Letters, 82(6), 293-298. Amsterdam: Elsevier.
• Lin, X. Y. (1992). Analysis of algorithms for drawing graphs. PhD thesis, Department of Computer Science, University of Queensland, Queensland, Australia.
• Luder, P., Ernst, R., & Stille, S. (1995). An approach to automatic display layout using combinatorial optimization algorithms. Software – Practice and Experience (25)11, 1183-1202.
• Marti, R., & Laguna, M. (2003). Heuristics and meta-heuristics for 2-layer straight line crossing minimization. Discrete Applied Mathematics, 12(3), 665-678.
• Matuszewski, C., Schönfeld, R., & Molitor, P. (1999). Using sifting for k-layer straightline crossing minimization. Lecture Notes in Computer Science; Vol. 1731: Proceedings of the 7th international symposium on graph drawing (pp. 217-224). London: Springer-Verlag.
• Miriyala, K., & Tamassia, R. (1993). An incremental approach to aesthetic graph layout. Computer-Aided Software Engineering, Proceeding of the Sixth International Workshop, Vol. 47. Iss 11, 1297-1309
• North, S. C. (1995). Incremental layout in DynaDAG. Software and Systems Research Center. AT & T Bell Laboratories.
• North, S. C., & Woodhull, G. (2001). On-line hierarchical graph drawing. Lecture Notes in Computer Science; Vol. 2265: Revised papers from the 9th international symposium on graph drawing (pp. 232-246). London: Springer-Verlag.
• Patarasuk, P. (2004). Crossing reduction for layered hierarchical graph drawing. Masters thesis, Florida State University, Tallahassee, Florida.
• Rabani, Y., (2003). Approximation Algorithms Lectures. Retrieved May 02, 2007 from http://www.cs.technion.ac.il/~rabani/236521.04.wi.html
• Raitner, M. (2004). Maintaining hierarchical graph views for dynamic graphs. Technical Report, MIP-0403, University of Passau, Passau, Germany.
• Rudell, R. (1993). Dynamic variable ordering for ordered binary decision diagram. In Proc. International Conference on Computer-Aided Design (pp. 42-47).
• Ryall, K., Marks, J., & Shieber, S. (1997). An interactive constraint-based system for drawing graphs. Mitsubishi Electric Research Laboratory.
• Stallman, M., Brglez, F., Ghost, D. (2001). Heuristics, experimental subjects, and treatment evaluation in bigraph crossing minimization. Journal of Experimental Algorithmics (JEA), 6(8).
• Stedile, A. (2001). JMFGraph - A modular framework for drawing graphs in Java. Masters thesis, Graz University of Technology, Graz, Austria.
• Sugiyama, K., Tagawa, S., & Toda, M. (1981). Methods for visual understanding of hierarchical systems. IEEE Trans. On System, Man, and Cybernetics, (2), 109-125.
• W3C. (1999) Glossary of Terms for Device Independence. Retrieved March 20, 2007 from http://www.w3.org/TR/di-gloss/
• Weisstein, E. W. (2003). Independent Set. MathWorld--A Wolfram Web Resource. Retrieved October 20, 2006 from http://mathworld.wolfram.com/IndependentSet.html
• West, D. B. (2001). Introduction to graph theory. New Jersey: Prentice Hall.
• Yehuda, B. (2000). One for the price of two: A unified approach for approximating covering problems, Algorithmica 27(2), 2000, 131-144.

Resources

• NIST Database
• Standford Graphbase
• Atlas of Cyperspaces