A New Force-Directed Graph Drawing Method Based on Edge-Edge Repulsion

Chun-Cheng Lin and Hsu-Chen Yen

​

Department of Electrical Engineering, National Taiwan University, Taiwan, R.O.C.

Outline

• Introduction and motivations

​

• Model of edge-edge repulsion

​

• Implementation and experimental results

​

• Conclusion

Force-directed graph drawing method

• An energy model is associated with the graph
• Low energy states correspond to nice layouts
• Hence, the drawing algorithm is an optimization process

Initial (random) layout

Final (nice) layout

Iteration 1:

Iteration 2:

Iteration 3:

Iteration 4:

Iteration 5:

Iteration 6:

Iteration 7:

Iteration 8:

Iteration 9:

Aesthetical properties

• Proximity preservation: similar nodes are drawn closely
• Symmetry preservation: isomorphic sub-graphs are drawn identically
• No external influences: “Let the graph speak for itself”

( This slide comes from Yehuda Harel )

Motivations (1/2)

• The force-directed methods can be categorized according to the types of repulsion

X ( vertex-vertex repulsion )

1.1. Eades, 1984

1.2. Fruchterman & Reingold,

1991

X ( vertex-edge repulsion )

2.1. Davidson & Harel, 1996

2.2. Bertault, 1999

1.1. Vertex-Vertex Repulsion�( Eades, 1984 )

• Model of Vertex-Vertex Repulsion
• Nodes → charged rings

→ repulsive force

• Edges → springs

→ attractive force

​

​

• Properties
• The drawing has a high degree of symmetry and uniform edge length

let go!

1.2. Vertex-Vertex Repulsion�( Fruchterman & Reingold, 1991)

• Eades’ force formulas
• Hook’s law for spring forces
• f_a( x ) = K ⋅ ( x – d )

⇒ Modified formula

• Newtonian law for repulsive forces
• f_r( x ) = K / r²

​

• FR proposed a more efficient version

​

• Locally consider vertex-vertex repulsion

2.1. Vertex-Edge Repulsion�( Davidson & Harel, 1996 )

• Drawing graphs using simulated annealing approach
• Using the paradigm of simulated annealing

(Kirkpatrick, Gelatt, and Vecchi, 1983)

• Their approach tries to find an optimal configuration according to a cost function as follows:

​

2.2. Vertex-Edge Repulsion�( Bertault, 1999 )

• A force-directed approach that preserves edge crossing properties
• Theorem. Two edges cross in the final drawing iff these edges crossed on the initial layout

#(crossings) = 5

Motivations (2/2)

• Def. Angular resolution
• the smallest angle formed by two neighboring edges incident to the common vertex in straight line drawing
• guaranteeing that arbitrarily small angles cannot be formed by adjacent edges

​

• The Zero Angular Resolution Problem
• There exist at least two of the edges incident to the common vertex overlapping
• Resulting in a bad drawing with edge-edge and vertex-edge crossings simultaneously
• Classical force-directed method cannot guarantee the absence of any overlapping of edges incident to the common vertex

initial

final

Model of Edge-Edge Repulsion

In each iteration:

• Step1. For each edge (spring),

compute spring forces as Eades’, i.e.

• Step2. For each pair of neighboring edges,

compute repulsive forces according to our model

• Step3. Adjust the position of every vertex according to the force

acting on the vertex

Every edge is replaced by

a changed spring.

Intuition

• The magnitudes of the repulsive force due to the two edges and are
• Positively correlated with the edge lengths
• Negatively correlated with the included angle θ

​

θ

Potential Field Method

• Motion planning or Path planning

( Chuang and Ahuja, 1998)

+

+

S

G

Reasons to simplify the repulsive force formula

• We don’t use the general formulas of edge-edge repulsion because:
• The formulas derived from potential fields appears to be a bit complicated and consequently require special care when implementing such a method. From a practical viewpoint, such a complication may not be needed for the purpose of drawing graphs.

​

• Therefore, by observing some characteristics of edge-edge repulsion and experimental results of potential fields method, we are able to derive a simplified version of repulsive forces.

Simulation on magnitude of force

Force magnitude vs. edge length

Force magnitude vs. the included angle θ

Simulation on orientation of force

the included angle α

the included angle θ

Simplified force formula

• The force can be calculated as:

​

​

​

• Note that f₁ has the advantage that f₁ is determined only by three parameters , facilitating a simple implementation of our drawing algorithm based upon edge-edge repulsion

​

Experimental Results (i)

• Larger angular resolution

​

​

​

​

• Preserve a high degree of symmetry and uniform edge length as the classical method

​

Experimental Results (ii) Hypercubes

Because the model of edge-edge repulsion allows at least two

vertices coinciding (although such drawings are improper),

our approach may produce drawings with more symmetries.

Statistics

• The following is the statistics of the above experimental results with comparison of the classical method and our approach. Observing the column StdDev / AvgLen, i.e. the normalized standard deviation of edge lengths, our approach without costing more running time seems to have equal or more uniform edge length than the classical method.

​

• Observing the column `Angular resolution’, the classical method may have the problem of zero or few angular resolution, while our approach normally has larger angular resolution than the classical.

Local minimal problem

• Force-directed method suffers from the local minimal problem, in which the spring force may be too weak to spread the graph

​

• Both the classical method and our approach may not handle local minimal problem in some cases, so the following strategies can be applied:
• Two-phase method
• First using the classical method and then using our method
• Hybrid strategy
• Simultaneously using the classical method and our method
• Adjusting parameters
• Parameters play important roles

( The figures shown in this slide comes from Yehuda Harel )

Conclusion

• A new force-directed method based on edge-edge repulsion for generating a straight-line drawing not only preserving the original properties of a high degree of symmetry and uniform edge length but also without zero angular resolution has been proposed and implemented

​

• Future work
• To handle the local minimal problem
• Try to use multilevel techniques or optimal heuristics, such as simulated annealing, genetic algorithm, etc.
• More experimental results on graphs of huge size and theoretical results on the power of the model of edge-edge repulsion

The End

Thank you for your attention.