Introduction

The On-line Hierarchical Graph Drawing Framework

(North et al., 2001) because it directly influences the design of the proposed constrained on-line graph framework (CGF). The on-line hierarchical graph drawing framework is a client-server system, in which clients communicate with the server via a set of operations as follows: insert, modify, delete sub-graphs. According to North and Woodhull (2001), more complex operations can be decomposed into those primitive operations. To enable the client-server communication, the on-line hierarchical graph drawing framework uses a shared graph model that is stored in a relational database. This graph model contains both geometric coordinates and layout attributes as shown in Table 10. The coordinates stored in the graph model are dimensionless, which allows clients to compute the physical precisions based on the client computer’s screen resolution. The vertex object has a constraint flag which allows clients to set a constraint on the vertex if needed.

Value	Type	Explanation
G = (V, E)	Graph object	Graph
u, w, w, ….. V	vertex object	Vertex
E,f, …. E	Edge object	Edge
Δ (G)	coordinate	Min vertex separation
Li, j	Vertex object	jth vertex in ith level
rx, ry	Float	Precision
λ (v)	Integer	Level rank assignment
X (v), Y (v)	coordinate	Position of vertex center
(v), Ŷ (v)	coordinate	Client vertex position request
	coordinate	Previous vertex position
B (v)	Coordinate	Vertex shape bounding box
Fixed (v)	Boolean	Vertex movable
Tail(e), head(e)	Vertex object	Endpoints
C(e)	Coordinate list	Layout spline
(e)	Coordinate list	Client request spline
ω (e)	Float	Weight 0
δ (e)	Float	Minimum length 0
Strong (e)	Boolean	Strong level constraint

The on-line hierarchical graph drawing framework was designed such that the client can submit requests for either each operation or a collection of operations to the server. The server will then invoke a function called Process which will run the modified Sugiyama heuristic updating the graph model. Once the update operation is complete, the server will send a response to the client that will trigger the client to render the layout.

To update the graph model based on requests from clients, the on-line hierarchical graph drawing framework utilizes a modified version of the Sugiyama heuristic for redrawing sub-graphs resulting from update operations. In addition to using the Sugiyama heuristic, the on-line hierarchical graph drawing framework does take into account the aesthetic criteria for incremental graph layout such as layout stability while computing each phase of the Sugiyama heuristic. North and Woodhull (2001) mention that applying these aesthetic criteria in computing the graph layout is based simply on notions of heuristic because there was no real experiment on how users understand graphs. North also points out that these aesthetic criteria are not comparable and are handled in different phases of the Sugiyama heuristic. Additionally, each phase in the Sugiyama heuristic needs at least a small amount of information from the previous phases. Hence there is no unified optimization equation that covers all the aesthetic criteria, but a collection of optimization problems for each phase in the Sugiyama heuristic.

The modified Sugiyama version used in the on-line hierarchical graph drawing framework has four phases just as does the original Sugiyama heuristic. Each phase is defined as an optimization problem. As showed in Table 11, the incremental graph layout aesthetic criteria are used as constraints in each phase of the Sugiyama heuristic.

Phase	Objective	Constraints
Re-rank	Min
ReduceCrossings	Crossings
UpdateGeometry	Min

The re-ranking vertices phase is similar to the layer assignment step in the Sugiyama heuristic. To preserve layout stability, the on-line hierarchical dynamic graph framework maintains an auxiliary graph called CG_y, whose vertices are interpreted as variables and edges as constraints, as shown in Tables 12 and 13 (North et al., 2001).

Variable	Explanation
	Level of v or Y (v)
	Stable level assignment of v
	Lower endpoint of weak edge
	Lowest and highest levels

Constraint edge	Weight	Explanation
	0	Maintain min level
	0	Maintain max level
		Strong edge constraint
		Weak edge constraint

To solve this optimization problem, the on-line hierarchical dynamic graph framework employs the integer network solver developed by the graph layout program called Dot, a program that draws static graph layouts. To reinforce hierarchical layout consistency, such as edges flowing in the same direction, the re-rank algorithm defines two types of edge constraints: the weak and strong level assignment constraints. Edges with strong level assignment are hierarchical and point downward. Edges with weak level assignment may point upwards or sideways. Weak edges have high cost c_rev as shown in Table 9. End users can explicitly define the level assignment constraint on the edges- if needed. North also points out that the network simplex solver does not take into account the stability constraint. To compensate, the re-rank algorithm includes explicit variables and constraints that penalize level assignment by their variance from their previous layout coordinates. These constraints provide a tradeoff between minimizing the edge length and maintaining geometric stability. The pseudocode of the re-rank algorithm is shown in Table 14.

procedure rerank(G: input graph) { for (e edgeDelections(G) ) { if (e is strong constraints) { remove constraint edge representing e in CGy; } else { remove ρ(e) and incident edges from CGy; for (v vertexDeletions(G)) { remove (v), and incident edges from CGy; } for (v vertexUpdate(G)) { (v)  mapToRank(requesCoord(v)) if ( isaStringMove(v)) { for (e incident on V) { remove constraint edges representing e in CGy; Create edge aux0 = , Tail(e) with (aux0)=crev(e); Create edge aux1 = , head(e) with (aux1)=crev(e); } } stabilize(v); } } } }

The reducing edge crossing phase includes several steps. First it determines which graph objects need any adjustments due to the update operations. Then it applies the crossing reduction algorithm. The on-line hierarchical dynamic graph drawing framework employs two different sort algorithms, median sort and transposition sort, to sort the vertices. The pseudocode is shown in Table 15.

Table 15. The pseudocode of the reduce crossings problem

procedure rerank(G: input graph) { pass  0; best  crossing(M); for (e edgeDelections(G) ) { if (e is strong constraints) { remove constraint edge representing e in CGy; } else { remove ρ(e) and incident edges from CGy; for (v vertexDeletions(G)) { remove (v), and incident edges from CGy; } for (v vertexUpdate(G)) { (v)  mapToRank(requesCoord(v)) if ( isaStringMove(v)) { for (e incident on V) { remove constraint edges representing e in CGy; Create edge aux0 = , Tail(e) with (aux0)=crev(e); Create edge aux1 = , head(e) with (aux1)=crev(e); } } stabilize(v); } } } }

In the update geometry phase, the on-line dynamic graph drawing uses the same integer network simplex solver. The variables and constraints are listed in Tables 16 and 17.

Table 16. The variable constraints

Variable	Explanation
	The left boundary of the layout
	X coordinate of vertex v
	Left point of e
	Stable anchor of v
S(Li, j)	Width of Li, j

Table 17. The variable constraints

Variable	Explanation
	Maintain left boundary
	Separate adjacent vertices
	Maintain left boundary
	Maintain leftmost vertex of e
	Maintain leftmost vertex of e

The objective function is