Force-directed graph drawing

Typically, spring-like attractive forces based on Hooke's law are used to attract pairs of endpoints of the graph's edges towards each other, while simultaneously repulsive forces like those of electrically charged particles based on Coulomb's law are used to separate all pairs of nodes.

Repulsive forces may be placed on edges as well as on nodes in order to avoid overlap or near-overlap in the final drawing.

For forces defined from springs whose ideal length is proportional to the graph-theoretic distance, stress majorization gives a very well-behaved (i.e., monotonically convergent)[5] and mathematically elegant way to minimize these differences and, hence, find a good layout for the graph.

Such mechanisms, which are examples of general global optimization methods, include simulated annealing and genetic algorithms.

The following are among the most important advantages of force-directed algorithms: The main disadvantages of force-directed algorithms include the following: Force-directed methods in graph drawing date back to the work of Tutte (1963), who showed that polyhedral graphs may be drawn in the plane with all faces convex by fixing the vertices of the outer face of a planar embedding of the graph into convex position, placing a spring-like attractive force on each edge, and letting the system settle into an equilibrium.

[14] Because of the simple nature of the forces in this case, the system cannot get stuck in local minima, but rather converges to a unique global optimum configuration.