Introduction

Barriers and Issues

There is an inherent trade-off between satisfying the layout stability aesthetic criterion and reducing the number of crossings or readability criterion. Preserving layout stability could increase the number of crossings, but reducing crossings can compromise the aesthetic criteria (North & Woodhull, 2001; Forster, 2004; Gorg 2005).

Another trade-off is between the aesthetic criteria and the space-time complexity. Satisfying the aesthetic criteria can increase the complexity of space or time or both (Cohen et al., 1992; Gansner, North, & Vo, 1993). Thus, in exploring the trade-off between minimizing the number of crossings and satisfying the aesthetic criteria, this dissertation seeks a solution that balances layout stability with minumum edge crossing numbers.

None of the research in dynamic graph drawing applications addresses the scalability of the use of internal data structures that capture the previous states of the graph layout. This leads to another interesting problem: how to construct an efficient graph model that enables the algorithm performance to be efficient and scalable for large graphs.

Other issues relate to the inconsistency between theoretical results and real world applications. Results from several experiments show that some proposed heuristics solving the problem have good performance when tested using synthetic data but have poor performance using real world data (Marti & Laguna, 2003). For instance, the median approach has better worst-case scenario efficiency than the barycenter approach, but the barycenter method outperforms the median method in practice.

One issue relates to the generation of graph models used in testing. Stallman, Brglez, and Ghost (2001) mention that finding a collection of graph data using a random graph generator that covers different types of graph is challenging. Results from several experiments also indicate that experimental results using synthetic graph data do not necessarily reflect those of real world graph applications (Marti & Laguna, 2003). Thus, generating graph data closely similar to real world graph applications poses an interesting but challenging problem for measuring the performance of the proposed heuristic.

The current literature lacks detailed information for solving the layer-by-layer crossing reduction problem. Most of the literature only vaguely describes the solution for the layer-by-layer sweeping approach. The recent experiment done by Patarasuk (2004) shows that the numbers of crossings sometimes increases after a sweep but then decreases again after another sweep. Thus, the lack of clear halt criteria in the layer-by-layer crossing reduction algorithm poses an interesting problem.

Most researchers assume that minimizing the number of edge crossings will improve the readability of the layout but the recent study by Huang and Eades (2005) shows that in some cases graph layouts with more edges crossings due to some constraints are easier to understand than the same layout with fewer edge crossings. The result of their experiments shows that human perception can be very complex. In real world graph application, minimizing edge crossings may not necessarily improve the users’ understanding of a layout. Hence, an alternative approach that balances between minimizing the crossing number and the user’s defined constraints could provide a more pleasant graph layout.

Formalizing aesthetic criteria is not feasible because some of the criteria are simply based on human perceptions. This unfeasibility was summarized by D. E. Knuth in the Graph Drawing conference 1996. His summary is that although merging aesthetic criteria and mathematical algorithms in graph drawing create a perception of harmony, formalizing aesthetic criteria as a mathematical equation is not feasible.

Limitations of the Study

Most commercial data are proprietary so the data that will be used for testing

the proposed constrained graph drawing system and the heuristic for constrained one-sided two-layered crossing reduction problem will either come from public domains or be synthetically generated. As discussed in the barrier and issues section, generated graph data may not reflect closely that of real-world applications.

Real world applications such as enterprise process modeling should support concurrent actions such as updating the graph structure. The constrained graph drawing framework proposed in this thesis will not take into account possible concurrent executions of editing the graph structure. This feature will be discussed in chapter 5 as a further enhancement.

Though real world graph data have different types of shapes and sizes, the proposed incremental hierarchical graph drawing framework will assume that the sizes are zero and shapes are simple circles for this thesis. However, the proposed framework will be designed such that the framework is extensible and accepts different sizes and shapes of vertices. The enhancement of the proposed framework will be presented in the recommendation section.