Improvements of graph data visualization using dynamics models

The most important problem for graph data visualization is the node layout problem. We have presented techniques for this problem, that apply some dynamics models, such as a spring model (like Hook's law) and a molecular model (like Van del Waals model).

Research contents

Quality of graph data visualization strongly depends on the result of node layout techniques. To develop useful node layout techniques, we first defined three conditions for the problem as follows.

[Condition 1] Distances between adjacent nodes are kept more than the user-specified value.
[Condition 2] The sum of lengths of arcs is minimized.
[Condition 3] Intersections between arcs and nodes are avoided.

Let us compare the layout results as follows. Left figure shows a result which does not satisfy the above conditions, and right figure shows a result which saticfies the conditions. Obviously the right result looks clearer.

Layout results which does not satisfy the conditions.	Layout results which satisfies the conditions.

Several previously proposed methods obtain somewhat preferrable layout results in reasonable computation times, by using dynamics models. These methods apply the following models, and obtains the configulations of nodes by solving an equation of motion with the forces:

• A molecular (repulsive) force for nodes. It works to preserve distances between adjacent nodes adequate.
• A spring (repulsive or attractive) force for arcs. It works to preserve lengths of arcs adequate.

We have implemented the method and found the following important problems:

• Computation time is not so low that the method is not always applicable to interactive applications.
• Quality of layout results strongly depends on the initial configulation.
• The number of intersections between nodes and arcs is not always small. See [Condition 3].

[Improvement 1]
An incremental algorithm that puts nodes onto a display space one-by-one.

Our algorithm is efficient because it localizes the force calculation. In our experiments, this algorithm is four or five times faster than the previous algorithms that scatters all nodes at the initial stage.
Moreover, our algorithm improves the quality of layout results, because it automatically defines the order of putting nodes so that hub nodes (that have many connections) are located at the center of a layout space, and terminal nodes (that have less number of connections) are located at the edge of the space.

The following examples show that our method improved the quality of layout result, and reduce the computation time.

Layout result by a previous method.	Layout result by our method.	Comparison of computation times.

[Improvement 2]
Bending of arcs to reduce the intersections between nodes and arcs.

This method first extracts arcs that have at least one node very close to the arcs. It then divides the arcs to small segments, and moves the endpoints of the segments by solving an equation of motion with the following three forces:

• A molecular force that preserves the distances between adjacent nodes and the endpoints of segments more than a user-specified value.
• A spring model that preserves the curvature of segments nearly constant.
• A spring model that preserves the length of segments nearly constant.

The following examples show that the method successfully reduces the intersections between nodes and arcs.

Before bending arcs.	After bending arcs.

We also applied the above improvements to hierarchical graphs. Our implementation first places nodes in top-level graph of the given hierarchical graph. It then repeats the layout process from higher-level to lower-level by the following procedure:

1. Place nodes in a lower-level graph.
2. Transfer the layout area of the lower-level graph to the corresponding node in the heigher-level graph.
3. Locally place again around the node.

Following image is an example of visualization of a website using our method. Here we constructed a hierarchical graph by mapping webpages to nodes and links to arcs. However, [Improvement 2] has not been applied to hierarchcal graphs.