force-directed: springs and charges
2026-05-18
force-directed layouts dominate graph visualization for one reason: they require no prior knowledge of graph structure. you don't tell the algorithm about communities, hierarchies, or clusters. you define forces, run a simulation, and the structure emerges from physics. a cluster of densely connected nodes will bunch together because the springs between them overpower the repulsion from distant nodes. a bridge node will settle between two clusters because it is pulled by both. the algorithm discovers topology without being told what topology to look for.
that emergent quality is also the source of its pathologies. this post covers both: how the physics works, what the math looks like, and the specific ways force-directed layouts fail.
the spring-and-charge model
the original formulation is Eades 1984. the idea is a direct physical analogy. treat every node as a charged particle. like charges repel, so every node pushes every other node away. then treat every edge as a spring connecting its two endpoint nodes. stretched springs pull their endpoints together; compressed springs push them apart.
let the simulation run. charged particles push the whole graph apart while springs pull connected pairs together. the system finds a state where those two pressures balance. nodes with many connections to each other end up close; nodes with few connections end up far apart; bridge nodes settle at the boundary between groups.
Eades's original spring force was logarithmic: f_spring = c1 * log(d / c2), where d is the distance between connected nodes and c1, c2 are constants. the repulsive force between all pairs was f_rep = c3 / sqrt(d). logarithmic attraction and inverse-square-root repulsion worked, but the constants were fiddly to tune and the behavior at small distances was numerically unstable.
Fruchterman and Reingold replaced both forces with simpler polynomials and introduced a single parameter that makes the scale legible.
fruchterman-reingold, step by step
the key insight in FR 1991 is to anchor both forces to a single "ideal edge length" k. define:
k = C * sqrt(area / n)
where area is the total drawing area (width times height), n is the number of nodes, and C is a scaling constant, typically 1. k is the length at which an edge is "happy": neither stretched nor compressed. it encodes the idea that nodes should be spaced so they collectively fill the available area.
with k in hand, the two forces become:
f_attraction(d) = d^2 / k (applied along each edge, pulls endpoints together)
f_repulsion(d) = -k^2 / d (applied between all pairs, pushes them apart)
d is the Euclidean distance between the two nodes in question. note the signs: attraction is positive (pulls inward), repulsion is negative (pushes outward). for a pair of connected nodes, the net force along their edge is d^2/k - k^2/d. that expression is zero when d = k, positive for d > k (pulling them closer), and negative for d < k (pushing them apart). the ideal edge length is the stable equilibrium point for each spring.
the cooling schedule
without a brake, the simulation overshoots. a node gets pushed or pulled, overshoots the equilibrium, gets pushed back, overshoots again. energy sloshes around indefinitely.
FR borrows a trick from simulated annealing: temperature. define a temperature t that starts at roughly the width of the drawing area and decays to zero over the iteration count. at each step, after computing the net force on every node, clamp the actual displacement to t:
displacement = min(|net_force|, t) * direction(net_force)
early iterations: t is large, so nodes can move far. large moves let the simulation escape obvious bad configurations: a node on the wrong side of the graph can cross over in a single step. late iterations: t is small, so nodes can only make tiny adjustments. the layout converges and stops jittering.
the default cooling is linear: t = t_initial * (1 - iteration / max_iterations). exponential decay works too and is what d3-force uses; the structural difference is that exponential decay never reaches zero, so the simulation needs a separate stopping condition. more on that in the d3-force section below.
the main loop in pseudocode
function fruchtermanReingold(nodes, edges, width, height, iterations) {
const area = width * height;
const k = Math.sqrt(area / nodes.length);
let temperature = width; // initial temperature = drawing width
for (let iter = 0; iter < iterations; iter++) {
// compute repulsive forces: all pairs
for (const v of nodes) {
v.displacement = { x: 0, y: 0 };
for (const u of nodes) {
if (u === v) continue;
const dx = v.x - u.x;
const dy = v.y - u.y;
const d = Math.sqrt(dx * dx + dy * dy) || 0.001;
const f = (k * k) / d; // repulsive magnitude
v.displacement.x += (dx / d) * f;
v.displacement.y += (dy / d) * f;
}
}
// compute attractive forces: along edges
for (const [source, target] of edges) {
const dx = target.x - source.x;
const dy = target.y - source.y;
const d = Math.sqrt(dx * dx + dy * dy) || 0.001;
const f = (d * d) / k; // attractive magnitude
const fx = (dx / d) * f;
const fy = (dy / d) * f;
source.displacement.x += fx;
source.displacement.y += fy;
target.displacement.x -= fx;
target.displacement.y -= fy;
}
// apply displacements, clamped to temperature
for (const v of nodes) {
const mag = Math.sqrt(
v.displacement.x ** 2 + v.displacement.y ** 2
) || 0.001;
const clamped = Math.min(mag, temperature);
v.x += (v.displacement.x / mag) * clamped;
v.y += (v.displacement.y / mag) * clamped;
// keep nodes inside drawing bounds
v.x = Math.max(-width / 2, Math.min(width / 2, v.x));
v.y = Math.max(-height / 2, Math.min(height / 2, v.y));
}
// cool: recompute from initial each step, do not compound
temperature = width * (1 - (iter + 1) / iterations);
}
}
the structure: repulsion outer loop (all pairs), attraction inner loop (edges only), displacement clamp, position update, temperature reduction. each iteration moves every node once. the number of iterations is typically 50 to 300 for small graphs; diminishing returns set in quickly after the temperature drops below a useful threshold.
kamada-kawai: minimize total energy instead
Fruchterman-Reingold is iterative and temperature-driven. Kamada and Kawai 1989 take a different approach: define a global energy function and minimize it directly.
the energy function is a sum over all pairs of nodes:
E = sum over all pairs (i, j) of:
(1/2) * k_ij * (d_ij - l_ij)^2
where d_ij is the Euclidean distance between nodes i and j in the current layout, l_ij is the ideal distance between them (proportional to their graph-theoretic shortest-path distance), and k_ij = K / l_ij^2 is a spring constant that makes nearby pairs in graph terms have stiffer springs than distant ones.
the ideal distance l_ij = L * graph_distance(i, j), where L is the desired unit edge length. computing all l_ij values requires all-pairs shortest paths: Floyd-Warshall at O(n^3), or Dijkstra from every source node at O(n * (m + n log n)), which simplifies to O(n^2 log n) on sparse graphs.
minimization proceeds via Newton-Raphson, one node at a time. pick the node m with the largest partial derivative of E (the node that is farthest from its energy minimum), solve for the delta that would zero its partial derivative, move it there, repeat until the maximum partial derivative is below a threshold.
the contrast with FR is instructive. FR simulates dynamics: forces, velocities, temperature. KK does calculus: gradient, Hessian, Newton step. FR converges roughly but quickly; KK converges precisely but requires solving a linear system per node per iteration.
for small graphs (up to a few hundred nodes), KK often produces more symmetric layouts because it is minimizing a single well-defined global objective. for large graphs, the O(n^2) setup cost and per-step linear algebra make it impractical compared to FR with its embarrassingly simple inner loop.
complexity: the n-squared per iteration
the pseudocode above has a nested loop: for every node, iterate over every other node to compute repulsion. that's O(n^2) per iteration. for n = 100 nodes, that's 10,000 pair evaluations per step. for n = 1,000 nodes, it's 1,000,000. for n = 10,000 nodes, it's 100,000,000, multiplied by however many iterations the simulation runs.
in practice, naive FR starts to crawl around 500 to 1,000 nodes and becomes unusable above that. the canonical solution is the Barnes-Hut approximation (part 2): build a quadtree over the node positions each iteration, and approximate the repulsion from distant clusters as a single force from the cluster's center of mass. that reduces repulsion computation from O(n^2) to O(n log n) per iteration. d3-force uses exactly this approximation in manyBody.js.
attraction stays cheap. the attractive force loop iterates over edges, not over all pairs. for sparse graphs (which most real graphs are), edge count m is O(n), so attraction is O(n) per iteration. the bottleneck is always the repulsion.
KK's complexity is different but not better: O(n^3) (Floyd-Warshall) or O(n^2 log n) (Dijkstra from each node, sparse case) for the all-pairs shortest paths in setup, then O(n^2) per full minimization pass: every node is visited, and each visit evaluates the gradient against all other nodes, which is the O(n) per node that compounds to O(n^2) per pass. it scales worse than FR plus Barnes-Hut.
failure modes: local minima and run-to-run drift
the energy landscape of a force-directed system is non-convex. many different node arrangements are locally low-energy, meaning that every small perturbation increases the energy, but the global minimum somewhere else in the configuration space might look completely different.
gradient descent, which is what FR approximates, always terminates at a local minimum. which local minimum you find depends on where you started. start from random positions and you get layout A. restart from different random positions and you get layout B. both A and B satisfy the force equilibrium condition. both are "correct" outputs. they look different.
this is not a bug to be fixed; it is a structural property of non-convex optimization. the mitigations are:
fix the random seed. if you initialize node positions using a seeded pseudorandom number generator and always use the same seed, you get the same starting configuration, which yields the same local minimum, which yields the same layout. deterministic behavior from a stochastic algorithm. d3-force uses an LCG (linear congruential generator) internally for exactly this reason, accessible via simulation.randomSource().
run multiple times, keep the best. run the simulation K times with different seeds, compute the total energy of each result, keep the layout with the lowest energy. expensive, but practical for small graphs where layout quality matters more than speed.
use spectral initialization. instead of random starting positions, initialize node coordinates from the eigenvectors of the graph Laplacian. spectral positions encode graph distance in Euclidean distance, which puts nodes in roughly the right neighborhood before the forces start. this dramatically reduces the number of bad local minima the simulation can fall into. the spectral initialization cost (O(n^2) to O(n^3) depending on the eigensolver) is often worth it for graphs where layout consistency matters.
run-to-run drift is a related but distinct problem. even with a fixed seed and identical inputs, the final layout can vary if the floating-point accumulation order changes between runs. this happens when threads process nodes in different orders (parallel force computation), or when the JS engine applies optimizations differently across sessions. the result: two runs with the same seed that should produce identical layouts produce subtly different ones. the differences are usually small (a few pixels), but they violate the determinism guarantee. the practical mitigation: iterate nodes in a fixed order (sorted by id, not by hash table order), and if you parallelize force accumulation, reduce results in a fixed order rather than letting threads commit as they finish.
non-convergence on certain topologies is the third failure mode. complete graphs (every node connected to every other) produce layouts where repulsion and attraction are almost perfectly balanced everywhere; the simulation wanders without settling. mitigation: weaken repulsion (lower the k constant) or add a bounding box force that pulls drift back to center. very regular graphs (grids, lattices) have many symmetry-related local minima of identical energy; the simulation oscillates between them. mitigation: break symmetry at initialization by adding small random perturbations to grid-snapped starting positions. long paths (chains of nodes, each connected only to its neighbors) produce layouts dominated by a single long strand where the cooling schedule may terminate before the chain straightens out. mitigation: increase the iteration budget, or use spectral initialization so the chain starts mostly aligned along the first non-trivial Laplacian eigenvector.
reading the source: d3-force
d3-force at commit c3e73cf6 is a clean reference implementation that makes the algorithm's moving parts visible.
the simulation loop in src/simulation.js shows how alpha (d3's name for temperature) updates and how positions advance:
a few things worth noting. alpha decays toward alphaTarget (default 0) each step: alpha += (alphaTarget - alpha) * alphaDecay. the default alphaDecay is 1 - pow(0.001, 1/300), which means after 300 steps alpha reaches 0.001 and the simulation halts. this is d3's cooling schedule: alpha plays the role FR calls temperature, but the decay is exponential rather than linear. each force function receives the current alpha and scales its output by it, so forces weaken as alpha falls.
velocityDecay (default 0.6, which means 40% velocity is retained each step) is a friction coefficient. in canonical FR, velocity isn't tracked: positions update directly from the clamped displacement. d3 uses velocity Verlet-style integration instead, accumulating vx and vy as velocity and then applying friction. the result is smoother convergence for the incremental, tick-based model that d3 targets.
the fx/fy check is node pinning: if a node has fixed coordinates, its velocity is zeroed and its position stays put. this is how d3 lets you anchor nodes without modifying the force computation.
the spring force in src/link.js shows attractive force computation:
the displacement vector (x, y) points from source to target. l = (l - distances[i]) / l * alpha * strengths[i] computes the scalar: how far the current distance deviates from the target distance, normalized to a unit-length direction, scaled by alpha and by a per-link strength. the default target distance is 30 pixels, not a function of area or node count. that's the main difference from canonical FR's k = C * sqrt(area / n): d3-force uses a fixed distance by default because it targets interactive, incremental simulations where the layout area isn't fixed ahead of time. you can supply a distance function to approximate the FR k formula.
bias[i] distributes the spring force between source and target in proportion to their degree counts. a high-degree source gets less of the push; a high-degree target gets more. this reduces the oscillation that high-degree hub nodes would otherwise cause.
the jiggle(random) call handles coincident nodes: if two nodes land at exactly the same position, x and y are both 0 and the direction is undefined. a small random perturbation breaks the tie.
papers to read next
Eades, P. (1984). "A Heuristic for Graph Drawing." Congressus Numerantium 42, pp. 149-160. the original spring embedder. logarithmic spring force, inverse-square-root repulsion. the paper that started the field. hard to find online; cite by reference.
Fruchterman, T. M. J., and Reingold, E. M. (1991). "Graph Drawing by Force-Directed Placement." Software: Practice and Experience 21(11), pp. 1129-1164. DOI: 10.1002/spe.4380211102. PDF: https://reingold.co/force-directed.pdf. the paper this post is mostly about. introduces the polynomial forces, the ideal edge length formula, and the temperature cooling schedule. the PDF is freely available. read the original derivation of k; the argument for why sqrt(area/n) is the right scale is cleaner in the paper than any summary.
Kamada, T., and Kawai, S. (1989). "An algorithm for drawing general undirected graphs." Information Processing Letters 31(1), pp. 7-15. DOI: 10.1016/0020-0190(89)90102-6. the energy-minimization alternative to FR. defines the spring energy in terms of graph-theoretic distance and minimizes via Newton-Raphson. the paper is short and the math is clean. worth reading alongside FR to see the two design philosophies side by side.
next: part 2 covers the Barnes-Hut approximation that reduces the O(n^2) repulsion computation to O(n log n), and the multilevel coarsening trick that scales force-directed layout to graphs with hundreds of thousands of nodes.