Introduction

The Constrained Crossing Reduction Problem

Forster (2004). As discussed in chapter 2, the constrained crossing reduction problem is a crossing reduction problem with respect to a set of constraints in which the order of some pairs of vertices on layer 1 is held fixed. For example, Figure 18 shows that a pair of vertices (u, v) forms a constraint denoted as c (u, v). The constraint is satisfied if b(u) > b(v) and vice versa, where b(u) is a barycenter value of vertex u.

Formally, let Let G = (L₁, L₂, E) be a two-layered hierarchical graph and a set of C = L₂ X L₂ constraints, where layer L₁ is fixed. Find permutation of vertices on layer L₂ so that the layout has few edge crossings and all constraints satisfied. This problem is also an NP-hard problem and a solution only exists if the constraint graph is acyclic (Forster, 2004). The author proposes a modified version of the barycenter heuristic in solving the constrained crossing reduction problem. The algorithm is based on a simple assumption such that if a constraint is violated then it is likely that there are more edge crossings between the two vertices. Hence, no vertex should be placed between the vertices if the constraint is violated. The modified barycenter algorithm is shown in Table 18.

procedure find_violated_constraints(Gc: constraint graph) { S  0; //active verticess for (v V ) { I(v)  {}; //empty list of incoming constraints if (indegree(v) == 0) { S  S  {v}; } } while (S <> 0) { choose v S; S  S – {v}; foreach (c = (s, v) I(v)) { if (b(v) > 0) return c; } foreach (outgoing constraint c = (v, t)) { I(t)  . I(t); if (|I(t)| == indegree(t)) S  S  {t}; } } return; }

Metrics for Measuring the Quality of the Incremental Graph Layout

(1) is minimal

(2) is maximal

Gorg (2005) points out that the two goals conflict one to another as illustrated in Figure 19. Optimizing both goals at the same time is not possible because achieving the drawing quality may destroy the layout stability and vice versa improving layout stability decrease the drawing quality by applying too much constraints on the layout algorithms. Thus, optimal goal is to find a trade-off solution. The model for constraint graph drawing framework is based on this model.

Figure 19. Two objective goals of incremental graph layout (Gorg 2005)

Abstract Model for a Constrained Graph Layout

where A represents consistency constraint, B represents readability constraint, C represents the layout stability, and w represents the importance of the criteria. The first two constraints – consistency and readability – represent the quality of a drawing. These two constraints are usually embedded within standard graph drawing algorithms for drawing a family of graph layouts. However, unlike the proposed model by Gorg (2005), the model for constraint graph layout also includes a notion of precedence or importance, which was proposed by North (1995), to ensure unique characteristics of a family of graph layouts. The importance of constraints influences the design of dynamic algorithms, which will be described in later sections.

Another difference between our model and the off-line model proposed by Gorg (2005) is the relationship between the readability and the layout stability. Based on the experience by Huang & Eades (2005), which shows that the reducing the number of edges crossings in some cases may not necessarily improving the readability criterion, we conclude that a relationship between the layout stability and the readability criteria is not simply linear but a non-linear relationship. We also notice that (1) consistency criterion is to adhere to rules defined by a layout characteristic (North 1995). For instance hierarchical layout requires vertices are in placed in horizontal layers and all the edges are as straight as possible points in the same direction. For orthogonal graph layout, all edges are drawn squarely as possible with few bended edges; (2) Consistency criterion does play a major role in a drawing quality; (3) it has higher precedence than that of layout stability. We hypothesize that the consistency criterion does affect the layout stability but the relationship between the consistency and layout stability does not necessarily linearly in the opposite direction as proposed by Gorg (2005). Assume that a relationship between the layout stability and the consistency criterion is linear and in an opposite direction, then it is impossible to achieve the layout stability goal because consistency criterion has higher precedence than that of the layout stability constraint and thus it shall override the layout stability constraint. However, the real world experiment shows that layout stability can be achieved even if the consistency constraint has higher precedence in the optimization problem. Formally,

Hypothesis:

A relationship between the layout stability and the consistency criterion is a non-linear relationship.

where is an optimization problem with three constraints. With . One can only maximize the consistency constraint with the cost of the C.

Based on these assumptions we model a relationship between the three constraints as a three dimensional relationship as shown in Figure 20, in which consistency and readability constraints improve drawing quality while the layout stability improve the global layout quality and their goals conflict one to another in a non-linear relationship.



Figure 20. A relationship between layout stability, readability, and consistency constraints

To translate the proposed abstract model to a concrete implementation for drawing different types of graph layouts, the constraints in the abstract model needed be incorporated into the standard graph drawing algorithms. We observe that both consistency and readability constraints are already a part of the graph drawing algorithms implicitly. For instance, the second step, layer assignment, in Sugiyama heuristic for drawing hierarchical graph layout implicitly covers the consistency criterion, and the third step, crossing reduction algorithm, improves the readability criterion. layout stability is usually incorporated into the graph drawing algorithms as a penalty parameter. The value of the penalty parameter is calculated based on the distance between the current layout and the previous layout in online dynamic graph layout and the current layout and the global layout in off-line dynamic graph layout. Well-known distance metrics that have been employed in incremental graph layout such as distance metrics, neighborhood metrics, orthogonal metrics. Most of the current works on incremental graph layout (Gorg 2005; Lee et al. 2006), use those aforementioned metrics as a primary measurement tool for computing the value of layout stability parameter. Few research (Bohringer et al. 1990) allows users to change the values if needed. Real world interactive graph drawing system, users sometimes set constraints on drawings. Furthermore, the layout aesthetic is not purely based on mathematics computation but also human perceptions. Our approach is to utilize both mathematic metrics and human perception and is similar to that of the proposal by Bohringer et al. (1990). The layout stability parameter in the optimization problem is defined as a dynamic feedback parameter, which is computed based on appropriate mathematic metrics, that is defined by the graph drawing framework, and also is override-able by end users. The Figure 21 shows the detailed description of the proposed model.