The Update Manager module in the server component is the core engine of the dynamic hierarchical graph drawing framework. It employs a modified version of the Sugiyama heuristic for the dynamic graph drawing framework and data from a relational database to update the graph layout locally and incrementally.
Since the aesthetic criteria influence the design of the dynamic graph drawing framework, the next section will review the aesthetic criteria prior to the design of the dynamic hierarchical graph drawing framework. The details of the software architecture will be discussed in a later section.
The graph-editing client initiates a communication with the Update Manager by sending an update request to the server through the TCP protocol. Upon receiving the request from the graph-editing client, the Update Manager transforms the XML message into a relational query and executes the query to return the affected graph data. The Update Manager then updates the affected vertices using a modified version of the Sugiyama heuristic. The Update Manager next updates the database with the new graph structure and sends the result back to the client.
The protocol for communication message between the editing client and the server is in XML format. The request message includes information about the vertices and the type of operations. The response message includes information about the vertices along with their logical properties. The logical properties of a vertex include but are not limited to (1) its layer, (2) its ranking within the layer, (3) shape, (4) text. Table 1 shows the XML schema of the request message and response messages.
Table 1. XML schema for the message protocol between the editing client and the Update Manager module
This module is a standard J2EE web application that runs on a J2EE web server and
handles HTTP requests and responses. The Visualization Manager accepts requests from graph visualization clients, transforms the requests into relational data queries, retrieves the graph data from the database, and returns a set of graph information in a XML format through the HTTP response. Figure 25 shows the communication between the visualization client and the Visualization Manager.
Figure 26. The communication between the visualization client and the Visualization Manager
The Visualization Client is a thin-client or web client application that will render the graph layout in the Internet browser. The thin client is a Java applet that supports viewing the graph layout.
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.
Davidson, R., & Harel, D. (1996). Drawing graphs nicely using simulated annealing. ACM Transaction on Graphics, 15(4):301-331.
Demetrescu, C., & Finocchi, I. (2003). Combinatorial algorithms for feedback problems in directed graphs. Information Processing Letters, 86(3), 129-136.
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.
Diehl, S., & Görg, C. (2002). Graphs, they are changing. Lecture Notes In Computer Science Vol. 2528 (23-30).
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.
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, 312-316.
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.
Gorg, C. (2005). Offline drawing of dynamic graphs. Ph. D Dissertation.
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.
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.
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.
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., Iss.
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.