Spring layout

The spring based algorithm is an algorithm for drawing graphs in an aesthetically pleasing way. Its purpose is to position the nodes of a graph in two dimensional or three dimensional space so that all the edges are of more or less equal length and there are as few crossing edges as possible.

The spring based algorithm achieves this by assigning a force to every edge, comparable to electric repulsion and attraction forces (or to springs in a mechanical system, hence the name of the algorithm). The entire graph is then simulated as if it were a physical system. The forces are applied to the nodes, pulling them closer together or pushing them further apart. This is repeated iteratively until the system comes to an equilibrium state, i.e. their relative positions do not change anymore from one iteration to the next. At that moment, the graph is drawn. The physical interpretation of this equilibrium state is that all the forces are in mechanical equilibrium; they do not exert a net force anymore.

The results of this algorithm usually look very good. The edges tend to have uniform length, and nodes that are not connected by an edge tend to be drawn further apart.

While graph drawing is a difficult problem, the spring-based algorithm is self-organizing and requires no special knowledge about graph theory such as planarity.

Another advantage of the algorithm is the interactive aspect. By drawing the intermediate stages of the graph, the user can follow how the graph evolves, seeing it unfold from a tangled mess into a good-looking configuration. In some interactive graph drawing tools, the user can pull one or more nodes out of their equilibrium state and watch them migrate back into position.

The major disadvantage of this algorithm is that it is very slow: order n squared where n is the number of nodes. This is because in every iteration, all pairs of nodes need to be visited and their mutual force needs to be computed.

Due to the physical analogy of masses and springs, it is easy to see that the spring-based algorithm produces a graph with minimal total energy. Faster algorithms exist, which minimise the total energy in more direct ways.