Force-based Algorithms (graph Drawing) - Disadvantages

Disadvantages

The main disadvantages of force-directed algorithms include the following:

High running time

The typical force-directed algorithms are in general considered to have a running time equivalent to O(n3), where n is the number of nodes of the input graph. This is because the number of iterations is estimated to be O(n), and in every iteration, all pairs of nodes need to be visited and their mutual repulsive forces computed. This is related to the N-body problem in physics. However, since repulsive forces are local in nature the graph can be partitioned such that only neighboring vertices are considered. Common techniques used by algorithms for determining the layout of large graphs include high-dimensional embedding, multi-layer drawing and other methods related to N-body simulation. For example, the Barnes–Hut simulation-based method FADE can improve running time to n*log(n) per iteration. As a rough guide, in a few seconds one can expect to draw at most 1,000 nodes with a standard n2 per iteration technique, and 100,000 with a n*log(n) per iteration technique. Force-directed algorithm, when combined with a multilevel approach, can draw graphs of millions of nodes.

Poor local minima

It is easy to see that force-directed algorithms produce a graph with minimal energy, in particular one whose total energy is only a local minimum. The local minimum found can be, in many cases, considerably worse than a global minimum, which translates into a low-quality drawing. For many algorithms, especially the ones that allow only down-hill moves of the vertices, the final result can be strongly influenced by the initial layout, that in most cases is randomly generated. The problem of poor local minima becomes more important as the number of vertices of the graph increases. A combined application of different algorithms is helpful to solve this problem. For example, using the Kamada-Kawai algorithm to quickly generate a reasonable initial layout and then the Fruchterman-Reingold algorithm to improve the placement of neighbouring nodes. Another technique to achieve global minimum is to use a multilevel approach.