Magnetic Fields next up previous
Next: Simulated Annealing Up: Force and Energy Controlled Previous: Gravity

Magnetic Fields

Spring embedders do not take into account edge directions. In directed graphs, all edges should point into the same direction when possible. Recently, Misue and Sugiyama [SuMi94, SuMi95] proposed an extension that enforces this effect: Edges are considered as springs, but also as magnetic needles which are oriented according to a magnetic field. Spring forces depend on the length of the edges and are parallel to the edges. A magnetic force additionally depends of the angle tex2html_wrap_inline2356 between edge and magnetic field, and is directed orthogonally to the edge. Thus, it rotates the edge. The magnetic force becomes zero when the edge points exactly in the direction of the field (Fig. 5). In the formula of magnetic forces, tex2html_wrap_inline2358 denotes the unit vector orthogonal to tex2html_wrap_inline2290 and the parameters tex2html_wrap_inline2362 and c allow to tune the force:

displaymath2354

   figure284
Figure 6: Magnetic Fields

Different magnetic fields have been used (Fig. 6). A parallel field can be used to give most edges a top down orientation (Fig. 7). The number of edges pointing against the field direction depends on the strength of the field; it is small but seldom minimal.

   figure311
Figure 7: Ternary Tree with Magnetic Field

A concentric field can be used to illustrate cycles in the graph (Fig. 8). Binary trees are often drawn in orthogonal layouts. A similar effect can be produced by a compound magnetic field where different sets of edges are influenced by different components of the field (Fig. 9). However, larger trees often produce edge crossings in the orthogonal field, such that this method is not perfectly suited for orthogonal drawings.

   figure325
Figure 8: Layout of Cube with Magnetic Field

   figure337
Figure 9: Layout of Binary Trees with Magnetic Fields


next up previous
Next: Simulated Annealing Up: Force and Energy Controlled Previous: Gravity

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