Next: Further work on the
Up: Graph layout algorithms
Previous: Layered layout
A forcedirected model is applicable to general undirected graphs. The idea is to model the vertices of the graph by physical entities that possess a repelling force. A good analogy is to imagine the vertices as charged balls that try to repel all other balls in the model. The edges of the graph are modelled with springs that are drawn further apart as vertices move away from each other. This model is demonstrated by work by Fructerman and Reingold in [20]. The algorithm then tries to minimise the energy states of the model with the underlying theory being that a relaxed system (that is a system possessing a minimum amount of energy) corresponds to readable layout, by achieving a majority of the aesthetic criteria defined for a good graph layout. The energy or stress of the system is minimised using different approaches, as is discussed later.
The example in Fig shows a connected graph
, first in a state of stress then in a state where the vertices in the graph are iteratively moved until no further improvement is possible, and the final output of the forcedirected graph is a system that is in a local minimum, giving a state of equilibrium.
Figure:
A graph showing the forcedirected analogy and it's corresponding parallel graph. Reproduced from [26]

Next: Further work on the
Up: Graph layout algorithms
Previous: Layered layout
20061107