Introduction
|
|  Yüklə 3.14 Mb.
|
SummaryThis section reviewed the key literature in two related areas of graph drawing frameworks, namely: (1) the Sugiyama heuristic with associated algorithms and heuristic, and (2) incremental graph drawing frameworks. The review of literature shows that most of the existing algorithms for solving the one-sided crossing reduction problem do not take the users’ constraints into account. Also there has been progress in incremental graph drawing frameworks for hierarchical graph layouts, but some of the user constraints such as stability criteria have been simply defined as a pure heuristic because too few experiments have measured how humans understand graph layouts. The newer research is now starting to pay attention to constraints that are defined by users. Recent study by Huang & Eades (2005) shows that user constraints do provide better readability for readers even if the resulting layouts may produce more edge crossings than layouts that do not capture user constraints. Other research like North (1995) shows that user constraints do help to ensure that graph layouts reflect graph semantics. However, none of the studies has addressed constrained crossing reduction in dynamic graph layouts, which is an important aesthetic criterion in graph drawing and graph visualization applications. Furthermore, most current proposals are limited to graphs with fewer than 50 vertices. As data grow quickly and the associations are getting more complicated, such as in Internet network and enterprise process modeling, a solution for rendering large graphs in a real-time environment is necessary for graph drawing and visualization frameworks. Contribution to the FieldThe work of this dissertation has several contributions to the graph drawing area, namely, (1) extend on-line dynamic graph drawing framework (North & Woodhull, 2001) by developing a framework for drawing and visualizing hierarchical directed graphs that supports large graph drawing and visualization efficiently, (2) develop a method to solve the constrained crossing reduction problem for dynamic hierarchical graph layouts. Chapter 3 MethodologyIntroductionThe work of this thesis includes four main tasks, namely (1) design and develop a framework for drawing and displaying hierarchical directed graphs by extending the on-line graph drawing framework developed by North and Woodhull (2001), (2) develop a mathematical model representing the aesthetic criteria constraints for incremental hierarchical graph layout, (3) develop a heuristic for the constrained crossing reduction problem for one-sided two-layered graphs based on the work of Forster (2004), and (4) evaluate the asymptotic complexity and efficiency of the newly developed heuristic for the constrained crossing reduction problem.
As the foundation of this thesis is based on the Sugiyama heuristic, the on-line hierarchical graph drawing framework (North & Woodhull, 2001), and the constrained crossing reduction algorithm (Forster 2004) as shown in Figure 16, this chapter shall first discuss important requirements and aesthetic criteria for drawing a good hierarchical graph layout. Next, the chapter shall discuss additional important aesthetic criteria in an incremental graph drawing framework such as layout stability. The chapter shall discuss the Sugiyama heuristic and its algorithms as some of these algorithms will be employed in the proposed constrained dynamic graph drawing framework. Next will be a review of the architecture and algorithms of the on-line dynamic graph drawing framework (North & Woodhull, 2001). For the second task, the chapter shall discuss the aesthetic criteria as constraints and review the previous seminal works in developing mathematical formulae for constrained graph layouts. The third task involves a review of the constrained crossing reduction problem and presents a variant version of the barycenter heuristic for the constrained crossing reduction problem proposed by Forster (2004) as preparation for the third task. After that, the chapter shall present the detailed architecture of a dynamic drawing framework for hierarchical directed graphs as a client server model. Also the chapter shall discuss a process for collecting graph data for testing. Finally, the chapter presents experiment procedures and a chapter summary. The remainder of this chapter is organized as follows:
 Figure 16. A two-layered hierarchical graph layout after crossing reduction is
|