Introduction

Dynamic Graph Drawing Systems

Bohringer and Newbery (1990) address two issues with standard graph layout algorithms. The authors point out that without user intervention or user predefined constraints, automatic graph layout algorithms cannot ensure the semantic meaning of the layout. The other issue is that most standard graph layout algorithms do not take into account the previous layouts when computing the next layout. Thus, a new layout may look much different from previous layouts and confuse the users. Bohringer and Newbery propose to use layout constraints to improve the stability of layouts. The proposed layout constraints can either be defined by the user or are based on previous layouts. The research shows that the proposed constrained graph layout does improve stability but the system needs improvements in efficiency and scalability. Also the proposed system does not address the constrained crossing reduction problem.

Cohen et al. (1992) suggest that a good graph drawing system should support two important characteristics, namely: (1) good performance when restructuring the graph layout, and (2) the ability to maintain the stability of the layout by not changing the layout drastically.  They propose a generic framework for drawing planar graphs for a variety of standard drawings, especially trees and series-parallel digraphs.  The authors also define a property for dynamic graph layout called smooth update.  This property represents the stability of the graph layout, which is later formalized by North (1995) in his proposed dynamic graph drawing framework. 

Luder et al. (1995) present a graph drawing application called Automatic Display Layout (ADL) that preserves the topology of the layout across sequential updates. The authors define a term, topological consistency, which is a measure of how consistent the graph layout is with preceding layouts. The authors consider the problem to be a combinatorics optimization problem and define a cost function that includes static and dynamic constraints.  Static constraints represent the aesthetic criteria and dynamic constraints represent the changes to the layout with respect to the previous layout. Their experience shows that the system can handle a graph of up to 50 vertices. However, the ADL system does not address how to minimize the number of crossings.

North (1995) formalizes the notion of smooth update and dynamic graph layout stability. The author defines three aesthetic criteria for measuring the effectiveness of a dynamic graph layout: (1) consistency, (2) stability, and (3) readability. Consistency means that the layout should adhere to the predefined business rules for a domain, stability requires minimal changes between successive layouts, and readability helps make the layout easier to comprehend (North, 1995).  Based on aesthetic criteria for dynamic graph layout, North (1995) proposes an incremental graph drawing system called DynaDAG based on the Sugiyama heuristic. The proposed framework preserves topological and geometrical stability during dynamic operations by applying constraints to each phase of the Sugiyama heuristic. The experimental results on small graph data indicate that the DynaDAG produces consistent layouts. However, scalability and the constraint crossing reduction are not addressed in the DynaDAG framework.

Ryall, Marks, and Shieber (1997) propose a constraint based drawing editor called GLIDE (Graph Layout Interactive Diagram Editor), which allows users to produce small or medium diagrams while the system maintains topological stability.  The GLIDE system enables users to interact with the system in real time and provides a set of hints called Visual Organization Features (VOF), a predefined set of common standard vertex placements. The GLIDE system uses Hook's Law to compute the graph layouts with respect to a set of constraints. Although the GLIDE system supports constrained graph layout, the system does not apply for drawing hierarchical graph layouts.

Extending the notion of the dynamic graph layout formalism proposed by North (1995), Brandes and Wagner (1997) proposed a generic framework for on-line dynamic graph layout by utilizing the random field. The authors define the layout models in term of the random field, in which layouts are assigned probabilities that reflects their conformance with the layout goals. The authors then use Bayesian decision system to solve this problem. The authors experiment with this framework on spring model and orthogonal drawings and conclude that the proposed framework can be adapted to other types of graph layout. However, the seminal work does not present the result of the experiment in term of efficiency and performance. At the time of this writing, there has not been an experiment using this framework on the Sugiyama heuristic.

He and Marriott (1998) address the problem with current graph layout algorithms: most of the existing algorithms were not designed for interactive graph drawing applications for two reasons. The first is that the graph layout should not be altered too much and should preserve the mental map by remaining stable.  Existing algorithms do not adhere to this criterion and thus destroy user orientation. The second is that existing algorithms do not support the application constraint, which is based on the semantics of the graph data structure.  The authors also propose four mathematical models for a constrained graph layout framework, where three models are for undirected graphs and one is for trees. 

Diehl et al. (2000) point out the disadvantages of graph animation and on-line dynamic graph layout. Graph animation technique simply shows the how vertices are moved to their new positions but does not necessarily preserve the metal map. Though the incremental or on-line graph layout does preserve layout stability, the next layout is based on the previous layout so in a worst-case scenario, the incremental graph layout has to compute the layout of the whole graph. The authors introduce an off-line dynamic graph layout algorithm called foresighted layout that preserves the mental map of the graph layout based on a global graph layout structure. This approach looks ahead and renders the entire sequence of n drawings with a respect to a global graph layout from a given sequence of n graphs with an assumption that the entire graph is known in advance. Gorg, Birke, Pohl and Diehl (2004) extend the foresighted layout framework in orthogonal and hierarchical graph layout. The experiment result indicates the framework is extensible to other types of graph layouts but the authors admit that it is difficult to apply a foresighted layout framework with graph layout models that are constructed through multiple phases such as hierarchical graph layouts. The seminal work does also not address the issues of efficiency and scalability of the foresighted layout.

Improving the efficiencies and performance of the DynaDAG framework (North, 1995), North and Woodhull (2001) propose an On-line Hierarchical Graph Drawing system.  The proposed system is a client server model, which allows the client to update incrementally using a messaging protocol.  To preserve the layout stability, the server maintains a shared graph model and updates the model upon client requests and according to the constraints imposed by the aesthetic criteria.  To apply the constraints on each phase of the Sugiyama algorithm, the authors define an objective function with a set of constraints for each phase and use a simplex network solver to solve the problems. Though the DynaDAG system presents a framework for an on-line hierarchical graph drawing system, it does not address the constrained crossing reduction problem.

Lee et al. (2006) propose an algorithm that preserves the mental map for general graphs based upon the simulated annealing graph drawing algorithm (Davison & Harel 1996). The modified simulated annealing algorithm includes six aesthetic criteria defined by Bridgeman and Tamassia (2002) to reflect the user’s mental map. The algorithm has three phases. The first phase is to apply the original simulated annealing algorithm to draw graphs. The second phase is to modify the graph slightly. The third phase is to redraw the graph subject to aesthetic criteria. The authors mention that this approach is flexible because it allows the end user to adjust the relative weight of each constraint in the algorithm.

Frishman and Tal (2007) propose an efficient and scalable new algorithm based on force directed layout for drawing on-line dynamic graph layouts. This proposed algorithm computes the layouts using a global layout structure. The authors note that by moving the main algorithm executions from CPU to GPU, the performance is faster than the conventional directed force algorithms. The result shows that the quality of the generated layouts is as good as the current directed force algorithms but it outperforms the standard algorithms. Table 4 shows the summary characteristic of each framework.