Further reading
These were the papers we found most useful:
"Graph drawing by stochastic gradient descent," Zheng et al., 2018
SGD rules! That's a platitude in the ML community, but apparently its a relatively new in its application to graph layout. In this paper, the authors adopt a spring model with ideal spring length between nodes proportional to their graph distance:
Using repeated constrain projection with a decaying learning rate, they are able to achieve much lower overall stress compared to existing methods, like force majorization.
"Efficient and high quality force-directed graph drawing," Hu, 2005.
This paper provides a great treatment of the difference between the Spring model (Kamada-Kawai) and Spring-Electrical model (Fruchterman-Reigold). It also show how the Spring-Electrical model can be made to work for graphs with a huge number of nodes by (1) using a quadtree-based approximation of long-range pairwise forces, (2) multilevel graph coarsening to lay out global clusters before focusing on local details.
"Scalable, versatile and simple constrained graph layout," Dwyer, 2009.
This paper describes a general class of Euclidean distance constraint that can be used to build a variety of higher-level constraints. The main idea is to enforce a distance between a pair of points, optionally after projection onto a specified axis vector:
It turns out that the gradient for this constraint is easy to compute geometrically, and through repeated iterative projection (inspired by computer simulation cloth models), can produce remarkably stiff constraint satisfaction.
"Octilinear force-directed layout with mental map preservation for schematic diagrams," Chivers & Rodgers, 2014.
This paper focuses on how force-directed techniques can be used to layout an octilinear metro map by enforcing edge orientation constraints. Rather than imposing the constraints from the start in addition with the repulsive/attractive forces, they induce a curriculum that interpolates between the two for the best results. We were curious about this paper because we greatly admire metro map design: it helps convey complex information to people in a digestable and often aesthetically pleasing way.
"Integrating edge routing into force-directed layout," Dwyer et al., 2007.
This paper covers how edges can be routed around obstacles on its way from its source to its target. We mainly chose this paper because we wanted to do edge routing to produce orthogonal edges and/or edges with few crossings. The technique uses stress majorization to reduce stress on a graph by moving nodes and edge bend points.