Force and Energy Controlled Placement next up previous
Next: Spring Embedding Up: Graph Layout for Previous: Notation

Force and Energy Controlled Placement


The simplest kind of graph layout is a straight line layout. All edges are drawn as straight lines between the centers of the adjacent nodes. Calculation of the layout reduces to the problem of finding node positions.

The main idea of the heuristic is to simulate physical-chemical models. Many objects occurring in physics and chemistry (e.g. molecules, crystals, combined inoperative pendulums, etc.) have a high degree of uniformity and balance. These are just the aesthetic criteria aimed at by a good layout method. The uniformity of physical-chemical objects is a result of the force and energy effects at the particles. The particles move according to the forces, and come to inoperative positions when the forces eliminate each other, and the physical system is balanced if the energy sum is minimal. In the heuristics, we consider the nodes as particles, start from an arbitrary initial position, simulate the movements of the nodes and lower the energy stepwise such that the nodes come to rest.

(1)  		 Set all nodes  tex2html_wrap_inline2236  to initial positions;

(2) for actround = 1 to maxrounds do

(3) Select a node tex2html_wrap_inline2236 ;

(4) Calculate the forces at v;

(5) Move v an amount tex2html_wrap_inline2278 into the direction of the sum of forces;

(6) Calculate the energy E of the system;

(7) if E is small enough then stop loop;

(8) od

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