ABSTRACT
Some of the most flexible algorithms for calculating layouts of simple undirected graphs belong to a class known as force-directed algorithms. Also known as spring embedders, such algorithms calculate the layout of a graph using only information contained within the structure of the graph itself, rather than relying on domain-specific knowledge. Graphs drawn with these algorithms tend to be aesthetically pleasing, exhibit symmetries, and tend to produce crossing-free layouts for planar graphs. In this chapter we will assume that the input graphs are simple, connected, undirected graphs and their layouts are straight-line drawings. Excellent surveys of this topic can be found in Di Battista et al. [DETT99] Chapter 10 and Brandes [Bra01]. Going back to 1963, the graph drawing algorithm of Tutte [Tut63] is one of the first force-
directed graph drawing methods based on barycentric representations . More traditionally, the spring layout method of Eades [Ead84] and the algorithm of Fruchterman and Reingold [FR91] both rely on spring forces, similar to those in Hooke’s law. In these methods, there are repulsive forces between all nodes, but also attractive forces between nodes that are adjacent. Alternatively, forces between the nodes can be computed based on their graph theoretic
distances, determined by the lengths of shortest paths between them. The algorithm of Kamada and Kawai [KK89] uses spring forces proportional to the graph theoretic distances. In general, force-directed methods define an objective function which maps each graph layout into a number in R+ representing the energy of the layout. This function is defined in such a way that low energies correspond to layouts in which adjacent nodes are near some pre-specified distance from each other, and in which non-adjacent nodes are well-spaced. A
Figure 12.1 Examples of drawings obtained with force-directed algorithms. First row: small graphs: dodecahedron (20 vertices), C60 bucky ball (60 vertices), 3D cube mesh (216 vertices). Second row: Cubes in 4D, 5D and 6D [GK02].
