Graph Visualization For Geography - Methods for Multilevel Analysis and Visualisation of Geographical Networks - page 78

6.2 General Graph Drawing Method

The most frequently used approach for laying out general graphs is the so-called
force-directed method that uses particles and attractive forces to model the nodes
and their edges in a network, respectively. The algorithm creates a physical
system and simulates its evolution to a state of equilibrium. Figure 6.1 shows a
representation of a physical system that models nodes with particles and their edges
with springs.
That method has become increasingly popular in recent years because it presents
some interesting advantages. First, the physical analogy is easy to understand for
practitioners without a background in graph theory. Thus, it generates visualizations
of graphs that can be shared and presented to large audiences. Second, the naive
implementation of this algorithm is straightforward, and one can easily modify
it and make customized versions to meet particular needs. Finally, this method
generates drawings that are visually pleasant, structurally significant and usually
better optimized than those obtained with other graph drawing algorithms.
When using this naïve approach (e.g., Eades , 1984 ; Frick, Ludwig, & Mehldau ,
1995 ; Fruchterman & Reingold , 1991 ), system convergence is quite slow and this
method is not useful for large datasets. Recent force-directed algorithms overcome
this limitation by making a trade-off between time efficiency and aesthetic criteria
(e.g., Gajer & Kobourov , 2002 ; Hachul & Junger , 2005 ; Lauther , 2007 ). In this
section, we first present the main classical force-directed algorithms and then
explain how to improve the time complexity of such algorithms.

6.2.1 Force Directed Drawing

In 1984 , Eades introduced the first algorithm based on the use of a force system.
His algorithm is initialized by placing the nodes at random positions. Then, at each
round, each node is moved in the direction of the attractive (springs) and repul-
sive forces (nodes). After several rounds, the system automatically converges to
equilibrium. The bottlenecks of this approach are the force computation complexity
and, in some cases, the system can oscillate and never reach equilibrium. Several

Fig. 6.1 Example of a physical system built using particles and springs to represent the nodes
and their edges, respectively. Particles create repulsive forces while springs create attractive forces
between particles