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

Gravity

It is obvious that connected components of a disconnected graph will move apart in a simple spring model because of lack of attractive forces. Often, loosely connected components are also positioned far from each other such that the edges in between are unaesthetically long. Thus, Frick e.a. introduce additional gravity forces [FLM95]. All nodes tex2html_wrap_inline2324 are attracted by the gravity to the barycenter (the average of all node positions p(v)):

displaymath2320

In the proposal of Frick e.a., gravity forces depend on the number tex2html_wrap_inline2328 of adjacent edges at a node v. Nodes with high degree are more important since they drag along many nodes in the same direction. The gravity force at a node can be defined as

displaymath2321

   figure183
Figure 2: Layout of Hexagonal Grid

   figure195
Figure 3: Layout with Gravity

Although gravity forces are attractive as of themselves, they are not a total replacement of spring forces. If only gravity and charge repulsion take effect, the nodes are placed evenly around the barycenter, but regularities of the edge structure are not visible (Fig. 2, left). Only the spring forces contribute to the symmetry of the layout.

   figure212
Figure 4: Layout of Multiplied tex2html_wrap_inline2218

Since gravity forces are polar directed to the barycenter, they enforce a round structure of the layout. Fig. 3 shows the effect of gravity on a grid graph. However, the main advantage of gravity is visible if the graph is partitioned into very dense parts which are loosely connected. Without gravity, the nodes of the parts are very close together but the parts themselves are far from each other. Thus, the edge lengths are not uniform. Gravity has the effect that the parts are positioned closer such that the layout is much more homogeneous (Fig. 4).

   figure226
Figure 5: Spring Force and Magnetic Force


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

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