Introduction
|
|  Yüklə 3.14 Mb.
|
|
Chapter 1 IntroductionGeneral hierarchical graph layouts as shown in Figure 1 are often used to display relationships between objects (North, 1995). Some examples of their use include entity relationship models in databases, the Unified Modeling Language (UML) in software engineering, management organizational charts, and hierarchical layouts in computer networking to display Internet networks (Battista, Eades, Tamassia, & Tollis, 1999; Cohen, Battista, Tamassia, Tollis, & Bertolazzi, 1992; North & Woodhull, 2001) 
Figure 1. A hierarchical graph layout Although current hierarchical graph layout algorithms have been well studied (North & Woodhull, 2001) and have been effective for drawing static graphs with fewer than 100 nodes, real world graph editing applications such as enterprise process modeling applications depict large amounts of complex data that change frequently but incrementally. Modelers who manage such large and complex models often incrementally update the model locally and expect a corresponding local change in the layout of the model without too drastic a change from the previous layout. Without this precaution users could be confused and unable to associate the new model with the previous model. In other words, the users' “mental map,” their perception of the graph’s concepts based on previous knowledge, could be destroyed if the next layout is substantially different from the previous layout. Thus, incremental stability is an important requirement of real world graph applications. Currently, most standard graph drawing algorithms tend to apply global optimization and redraw the entire graph when the graph data changes. The resulting layout sometimes can be quite different from the previous layout. Moreover, graph models of real world applications are often updated by some users while others are viewing the model on-line. To support both editing and viewing in real-time mode, graph editing applications need to not only generate incrementally stable layouts but to generate them as quickly as possible. Applying a global change on the model when a local change is made may not be scalable for large data models such as enterprise process models. As a result, the dynamic behavior of real world graph applications poses challenges for current graph drawing algorithms in terms of incremental stability and scalability. To address dynamic behaviors of real world graph applications such as incremental stability and scalability, Cohen et al. (1992) propose dynamic graph algorithms for different types of graph drawing techniques, especially series-parallel directed graphs and trees. Miriyala and Tamassia (1993) introduce an incremental graph drawing algorithm for drawing orthogonal graph layouts. Brandes and Wagner (1997) formulate dynamic layouts in terms of random field and present a formal concept for dynamic graph layouts. He and Marriott (1998) propose several models for constrained force directed graph layout. Diehl, Gorg, and Kerren (2000) present an off-line dynamic graph drawing framework called foresighted layout that renders a sequence of graph layouts from a given sequence of graphs while preserving the global layout. Lee, Lin, and Yen, (2006) present a modified simulated annealing algorithm that preserves the user’s mental map and ensures graph layout stability. Frishman and Tal (2007) propose a new on-line dynamic graph drawing that is based on a force directed layout algorithm. Examples of progress in hierarchical drawing for directed graphs in recent years include a hierarchical directed graph drawing system called on-line dynamic graph drawing (North, 1995; North & Woodhull, 2001), and hierarchical graph views for dynamic graph layouts (Buchsbaum & Westbrook, 2000; Raitner, 2004).
Problem StatementWhile incremental graph drawing algorithms such as on-line dynamic graph drawing (North & Woodhull, 2001) for drawing hierarchical graph layouts do improve layout stability, their aesthetic criteria impact the readability criterion by complicating the computation of vertex reordering on a layer. They also minimize the number of crossings by imposing certain constraints on vertices. In fact, the crossing reduction problem for dynamic hierarchical graph drawing is a variant of the crossing reduction problem called constrained crossing reduction, in which the crossing reduction algorithm works with a set of predefined constraints. This problem will be presented in chapter 2. Minimizing the number of crossings is one of the important criteria for measuring the quality of a graph layout algorithm, but unfortunately crossing reduction is an NP-complete problem (Garey & Johnson, 1983). Though there has been significant research in this area, most of the work has focused on developing heuristics to solve the crossing reduction problem without constraints on vertices. Moreover, the recent experiment done by Huang and Eades (2005) shows that in some cases a constrained graph layout that produces more edge crossings provides a better visualization than the same layout with fewer edge crossings. User constraints indeed impact aesthetic criteria and influence the design of the algorithm that solves the crossing reduction problem. Hence, minimizing the number of crossings on a constrained graph layout requires further investigation. Although several researchers propose efficient on-line dynamic graph drawing systems such as the on-line hierarchical graph drawing framework (North & Woodhull, 2001), those systems do not address the constrained crossing reduction problem. Further research is needed to address this problem and to improve the scalability and performance of the dynamic graph drawing algorithm, especially the crossing reduction problem as suggested by North and Woodhull (2001). The work in this thesis will develop an incremental graph drawing framework based on on-line dynamic graph drawing (North, 1995; North & Woodhull, 2001). The result of this research will improve the incremental stability and scalability of graph drawing systems.
|