next up previous
Next: Further work on the Up: Graph layout algorithms Previous: Layered layout

Force-Directed Layout

A force-directed 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 $ G$ , 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 force-directed graph is a system that is in a local minimum, giving a state of equilibrium.
Figure: A graph showing the force-directed analogy and it's corresponding parallel graph. Reproduced from [26]
Image springexample


next up previous
Next: Further work on the Up: Graph layout algorithms Previous: Layered layout
2006-11-07