Introduction

Hierarchical Constrained Graph Layout

Unlike algorithms for directed force layout model, hierarchical graph drawing algorithm are multi-phases. It is not feasible to have an optimization model or one set of constraints that covers all the phases in Sugiyama algorithm. North & Woodhull (2001) observe that there is no such unified model that represents the hierarchical graph drawing algorithm but the aesthetic criteria should be divided and formed different constraints in each phase of the Sugiyama algorithm. Gorg et al. (2004) also addresses the same issue with the hierarchical graph layout family when implementing Foresighted Layout algorithm for drawing dynamic hierarchical graph. Gorg et al. (2004) admitted there is no such global graph adjustment for hierarchical graph layout. Hence, the authors divide the adjustment into multiple phases according to the Sugiyama heuristic. Similar to the DynaGraph, an optimization problem for hierarchical constraint graph drawing is divided into different sub optimization problems for appropriate steps in Sugiyama heuristic. Thus, the constraints in the optimization shall be divided into different phase of the Sugiyama heuristic.

First step, which temporarily reverses the directions of edges, does not affect layout stability criterion so it does not need to include layout stability constraint. As the proposed constraint graph layout utilizes a relational data model to capture the graph structure, which includes edge direction, a set of edges need be reversed shall be identified automatically if any. The second step, layer assignment, does affect all three constraints in the optimization problem but only consistency and readability constraints are embedded within the algorithm. To compensate for the layout stability constraint, the layout assignment algorithm shall include a penalty parameter. In the same manor, the crossing reduction step affects readability and layout stability constraints and only readability is embedded within the crossing reduction algorithm. The layout stability constraint shall be included. Detailed descriptions of algorithms with additional penalty parameter is in the algorithm section.

The value of layout stability parameter shall be stored in a relational data model, which shall be defined in the next section, and be used in recalculating the next value of the layout stability when an update operation is performed. The formula for recalculating the layout stability value for each instance of layouts is as follows:

Let C_i C be a layout stability parameter for layout i, and a predefined threshold:

where is a threshold value that is set by the framework and can be overridden by the users. C_i is a stability parameter for layout i. Distance metrics depends on each step in Sugiyama heuristic.

A Relational Model for Constraint Hierarchical Graph Drawing

Table vertex_model represent vertices in the current snapshot of the hierarchical graph layout. This table associates with table named vertex_property through a vertex_id which is a primary key of the vertex_model table. Table vertex_property captures the characteristic of vertices such as width, height, color, shape type etc. In the same manor, table edge property store characteristics of an edge and associates with edge_model table, which represent edges in the current snapshot of the hierarchical graph layout. Both table vertex_snapshot and edge_snapshot are used to store a sequence of hierarchical graph layout. These two tables shall be used by visualization module for rendering graph layout.

Algorithms

Cycle Removal

Layer Assignment

procedure (G: sub-graph, w:positive interger) { all vertices  0; //no ordering for (i  1 to |V|) { choose an unlabelled vertex v such that {П(v): (u,v) E } is minimized; П(v)  i; } k  1; L1  1; U  0; while (U <> V) { choose u (V – U), such that every vertex in {v : (v, u) E } is in U, and П(u) is maximized; if (Lk < W and for every edge (u, w), w L1 υ L2 υ……..Lk-1) { add u to Lk; } else { k  k + 1; Lk  {u} } } }

Constrained One-sided two-layered crossing reduction

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; }