tags: #publish links: [[Graphic Design Resources]], [[Mathematics]] created: 2021-10-25 Mon --- # Force-directed graph drawing https://en.wikipedia.org/wiki/Force-directed_graph_drawing A physical-simulation-based way to auto-optimise graph layouts. First, create a model of simulated "forces" acting on nodes, e.g. some of these: - **Spring** - tension along edges, varying with length - **Charge** - repulsion from other nodes or edges, varying with proximity, like electrically charged particles - **Gravity** - attraction to a central point, or to similar kinds of nodes - **Magnetic field** - polarity-dependent forces e.g. for directed graphs - Twisting/tensile corner-straightening forces, if using curved edges ...then use the forces to compute or simulate to produce a graph layout: - **Iteratively simulate** the movements of the nodes under force, and resultant changes in forces, until a stable equilibrium state is reached. - or, **Analyse** the forcefields to directly compute an optimised or energy-minimised state You tune the layouts by adjusting the forces, e.g. linear vs log distances, changing the constants, etc. ## Benefits Easy to implement the naive version. Decent results, intuitive and simple, easily tuned. Lots of existing maths in this area, to adapt further. ## Drawbacks A simple, naive implementation has cubic complexity and doesn't scale to large numbers of nodes, but refined versions using hierarchical approximation and local slices can scale to millions of nodes. Sensitive to initial layout. Can get stuck in way-sub-optimal local minima. To avoid this, may need to compute an "ok" initial layout with one or more other algorithms first.