Spring Embedding next up previous
Next: Gravity Up: Force and Energy Controlled Previous: Force and Energy Controlled

Spring Embedding

The earliest heuristics of force-directed placement were based on the spring embedder model [QuBr79, Ea84]. Nodes are considered as mutually repulsive charges and edges as springs that attract connected nodes.

Let tex2html_wrap_inline2290 be the distance vector between two nodes v and w. Then, tex2html_wrap_inline2296 is the Euclidean distance. Between each pair of nodes, there are repulsive forces inversely proportional to the distance, e.g. the force vector


Between nodes connected by edges (v,w), there are attractive forces directly proportional to (a power of) the distance, e.g.


Different formulas for forces have been used in [QuBr79, Ea84, SuMi94, SuMi95], but the resulting effects are always similar. The parameters tex2html_wrap_inline2300 and tex2html_wrap_inline2302 allow to adapt the heuristics. An edge (v,w) is at equilibrium if tex2html_wrap_inline2306 . The length of the edge in this case is


Figure 1: Animation of Spring Embedding of Grid Graph

Although the algorithm does not explicitly support the detection of symmetries, it turns out that in many cases the resulting layout shows existing symmetries. If the iteration steps are animated, there is the impression of a three-dimensional unfolding process starting with a randomly produced bunch. The more symmetric a graph is, the more obvious is this effect. Fig. 1 shows the animation sequence of a regular grid graph.

Georg Sander
Thu Aug 1 15:27:34 PDT 1996