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 ecommerce graphing, where data increases rapidly, demand a comprehensive responsiveness when rendering the graph layout in a multiuser 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
 Dr. Laszlo, Michael (Main advisor)
 Dr. Sun, Junping
 Dr. Li, Wei
Sugiyama 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 oneside twolayered 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, 4351.
 Brandes, U., & Wagner, D. (1997). A Bayesian paradigm for dynamic graph layout. Proc. Measures for GSymp. Graph Drawing GD '97, pp. 236247.
 Bridgeman, S., & Tamassia, R. (2002). A user study in similarity measures for graph drawing. Journal of Graph Algorithms and Applications, 6(3), 225254.
 Buchsbaum, A. L., & Westbrook, J. R. (2000). Maintaining hierarchical graph views. Proceedings of the Eleventh Annual ACMSiam Symposium on Discrete Algorithms. 566575.
 Catarci, T. (1988). The assignment heuristic for crossing reduction. IEEE Trans. Syst. Man Cybern. 25(3), 515521.
 Coffman, E. G., & Graham, R. L. (1972). Optimal scheduling for two processors systems. Acta Informica 1, pp. 200213.
 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. 261270). Berlin: ACM.
 Demetrescu, C., & Finocchi, I. (2003). Combinatorial algorithms for feedback problems in directed graphs. Information Processing Letters, 86(3), 129136.
 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 (2330).
 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 2layered networks, Ars combin., pp. 187191. Proceedings of the Australian Computer Science Conference, 327334.
 Eades, P., Lin, X. Y, & Smith, W. (1993). A fast and effective heuristic for the feedback arc set problem. Information Processing Letters, 1215.
 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), 305325.
 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 twolayered crossing reduction. Proc. Graph Drawing, GD 2004, 206216.
 Frishman, Y., & Tal, A. (2007). Online dynamic graph drawing. Eurographic/ IEEEVGTC 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), 214230.
 Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NPcomplete. New York: W. H. Freeman.
 Garey, M. R., & Johnson, D. S. (1983). Crossing number is NPcomplete. SIAM Journal on Algebraic and Discrete Methods, 4(3), 312316.
 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, 289314. 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). 2layer straightline crossing minimization: Performance of exact and heuristic algorithms. J. Graph Algorithms and Applications, 1(1), 125.
 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), 293298. 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, 11831202.
 Marti, R., & Laguna, M. (2003). Heuristics and metaheuristics for 2layer straight line crossing minimization. Discrete Applied Mathematics, 12(3), 665678.
 Matuszewski, C., Schönfeld, R., & Molitor, P. (1999). Using sifting for klayer straightline crossing minimization. Lecture Notes in Computer Science; Vol. 1731: Proceedings of the 7th international symposium on graph drawing (pp. 217224). London: SpringerVerlag.
 Miriyala, K., & Tamassia, R. (1993). An incremental approach to aesthetic graph layout. ComputerAided Software Engineering, Proceeding of the Sixth International Workshop, Vol. 47. Iss 11, 12971309

North, S. C. (1995). Incremental layout in DynaDAG. Software and Systems Research Center. AT & T Bell Laboratories.
 North, S. C., & Woodhull, G. (2001). Online hierarchical graph drawing. Lecture Notes in Computer Science; Vol. 2265: Revised papers from the 9th international symposium on graph drawing (pp. 232246). London: SpringerVerlag.
 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, MIP0403, University of Passau, Passau, Germany.
 Rudell, R. (1993). Dynamic variable ordering for ordered binary decision diagram. In Proc. International Conference on ComputerAided Design (pp. 4247).
 Ryall, K., Marks, J., & Shieber, S. (1997). An interactive constraintbased 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), 109125.
 W3C. (1999) Glossary of Terms for Device Independence. Retrieved March 20, 2007 from http://www.w3.org/TR/digloss/
 Weisstein, E. W. (2003). Independent Set. MathWorldA 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, 131144.
Resources
