Force-directed layout draws graph vertices in two-dimensional space by treating edges as attractions and non-adjacent vertex pairs as distance-dependent repulsions. Updating positions toward equilibrium tends to produce similar edge lengths, fewer crossings, and an aesthetically useful embedding. section 16.5.1
The layout becomes an optimization problem: forces define a cost or energy landscape, and an iterative simulation adjusts vertex positions to reduce it. Gradient descent can reach a stable equilibrium without reaching the globally lowest-energy arrangement. section 16.5.1 section 17.3.2
A typical force-directed model combines:
- Attractive spring- or gravity-like forces between adjacent vertices. section 16.5.1
- Repulsive forces between every non-adjacent pair, usually dependent on their separation. section 16.5.1
- Position updates controlled by force formulas and parameters until the system stabilizes or an optimization method stops. section 16.5.1 section 17.3.2
The resulting drawing is useful because structure can become visible: a symmetric embedding may communicate relationships more clearly than a random placement. Simulated annealing can escape local minima, while hybrid methods such as GEM seek faster convergence. section 16.6 section 17.3.2
A composite layout cost
Davidson and Harel’s cost function combines vertex separation, distance from borders, edge length, vertex-to-edge separation, and edge intersections. Its parameters weight these competing objectives during layout.
