Introduction
|
|  Yüklə 3.14 Mb.
|
GoalThe objective of this research is (1) to develop a constrained graph drawing framework for drawing hierarchical graph layouts and (2) to develop a method to solve the constrained crossing reduction problem. The proposed dissertation shall extend the North and Woodhull (2001) research and develop a variant version of the on-line dynamic graph drawing system to achieve a solution that reduces the number of crossings while accommodating the set of constraining criteria proposed by North (1995). The specific goals of this research are as follows:
RelevanceGraph visualization and graph drawing play key roles in many applications across disciplines, such as relational database modeling, object oriented modeling or UML, business modeling, organizational diagrams, molecular layout, and DNA layout (Battista et al., 1999). With advances in computer hardware and the exponential growth of data, user experience with computer visualization is also getting more sophisticated. Some graph visualization applications have been ported to the Internet, whose environment is dynamic and whose users expect fast rendering of large graphs. Real world graph editing applications like enterprise process modeling tools require more sophisticated interactions such as inserting vertices into and deleting vertices from the graph (North, 1995) in real-time mode. More efficient and effective graph visualization algorithms are needed for visualizing larger graphs in real-time mode (Cohen et al., 1992; North & Woodhull, 2001; Buchsbaum & Westbrook, 2000; Raitner, 2004) while still fulfilling aesthetic criteria (North, 1995). Real-world graph structures are often dynamic and updated frequently (He & Marriott, 1998), but most standard graph drawing algorithms often apply global optimization, leading to unstable graph layouts. Moreover, most of those algorithms do not support incremental updating and thus do not scale well for displaying very large data sets or for graph layouts where users need to interact with the graph in real time. Research and studies have been undertaken to improve graph layout stability and performance. Bohringer and Newbery (1990) propose to use constraints that are defined by the user or are based on previous layouts to improve the stability of the layouts. Cohen et al. (1992) propose a dynamic algorithm for drawing planar graphs for a variety of standard drawings and define a property for dynamic graph layout called smooth update. Luder, Ernst, and Stille (1995) present a graph drawing application called automatic display layout that preserves the topology of the layout across sequential updates. He and Marriott (1998) propose a constrained graph layout framework for undirected graphs and trees. North (1995) proposes an incremental graph layout system called DynaDAG, which supports hierarchical graph drawing. There is a small difference between on-line and off-line dynamic graph layouts. An incremental, or on-line, graph drawing system preserves layout stability relative to the previous layout. On the other hand, an off-line dynamic graph drawing framework preserves layout stability relative to a global graph layout. Brandes and Wagner (1997) formalize the aesthetic criteria notion for dynamic graph layout introduced by North (1995) based on the random field model, which is widely used in imaging processing. The authors then propose a generic framework for on-line dynamic graph layout and experiment with the proposed framework by using spring models and orthogonal drawings. Buchsbaum and Westbrook (2000) formalize the concept of maintaining views for dynamic graph layout and propose efficient data structures for storing the views. Their research goal is to overcome the physical limitation of computer screen size by allowing users to focus on certain parts of the graph using expansion and contraction mechanisms while the underlying graph is subjected to edge insertions and deletions. Diehl et al. (2000) introduce an off-line dynamic graph layout algorithm called foresighted layout that preserves the layout stability based a global graph layout that is a union of all the layouts. This approach looks ahead and renders the entire sequence of n drawings with respect to a global graph layout from a given sequence of n graphs. Raitner (2004) extends the work of Buchsbaum and Westbrook (2000) and develops similar algorithms for maintaining large hierarchical graph layouts that are also subjected to leaf insertion and deletion operations. Lee et al. (2006) present a modified simulated annealing algorithm that preserves the user’s mental map by adding layout stability as a factor in the cost function in the simulated annealing computation. Similarly, Frishman and Tal (2007) propose a new algorithm based on force directed layout for drawing on-line dynamic graph layouts. The authors apply degree of movement flexibility on vertices to ensure the algorithm takes into account layout stability while recalculating the next layout. However, most techniques are applied to force directed graph layouts and few work well with hierarchical graph layout models. Within the few proposed frameworks for drawing hierarchical graph layouts, none of the current researchers present a way to minimize the number of crossings while accounting for a set of constraints imposed by criteria in dynamic graph drawing. The original contribution of the proposed dissertation is to develop a constrained graph framework for drawing hierarchical graph layouts that includes a heuristic that reduces the number of crossings for one-sided, two-layered directed graphs while satisfying the aesthetic criteria defined by North (1995). |