Graph

A readable graph respects aesthetic criteria of syntactic validity, perceptual organisation and aesthetic optimality as proposed by Kosak et al. in 1994. Some algorithms focus on minimising edge crossing whilst other focus on other aesthetic criteria.
Spring-embedded models and its variants fits aesthetic criteria. But which of them is the best?
First of all you have to define what best means. It depends on the scenario where the graph is used. Do you need a symmetric graph with lots of edge crossing, or to you need a graph to simulate molecular interactions? You have to give the answer! In this evaluation here best fits the following criteria:

1. Performance: Short calculation time of node placement
2. Scalability
3. Aesthetic criteria: Small number of edge crossing, optimal organisation of vertices.

I’m evaluating the upper criterias for an implementation in Javascript. Javascript is highly sensible on calculation complexity. Lots of calculations and look-ups break down the speed very fast. Short calculation time is very important.

As already mentioned spring-embeded models fits aesthetic criteria very well. Using spring embeded models fits the 3. criteria of aesthetics. Let’s evaluate the algorithms in respect criteria 1 and 2.

The Spring Model

The spring model was originally proposed by Eades (1984). The concept is easy. For all connected vertices a attractive force f_a(d) is calculated. A repulsive force f_r(d) is calculated among all nodes not connected.

• f_a(d) = k_a * log(d)
• f_r(d) = k_r / d²

d is the current distance between two nodes and k_a and k_r are constants.
Let be n the number of nodes and r the number of relations.
According to the implementation with Javascript a division is as expensive as a multiplication. But the calculation of a logarithm is 4 times more expensive then a multiplication or a division. The calculation time is:

(n * (1+1))²+ r * (1 + 4) = 4*n² + 5*r

The complexity is O(n²) because the repulsive force is calculated among all nodes.

The spring model is symmetric. It doesn’t try to reduce edge crossing. Reading those graphs could be problematic.

Force-directed Placement

The force-directed placement has been proposed by Fruchterman and Reingold (1991). This algorithm fits the criteria of minimised edge crossing. The spring model does not. This algorithm is based consists of attractive repulsive forces among nods. As in the spring model, attractive forces f_a are calculated between two connected nodes and repulsive forces f_r among all nodes.

• f_a(d) = d² / k
• f_r(d) = -k² / d

d is the distance between two nodes and k is the optimal distance betweent two nodes. k is calculated by the number of nodes and the drawing area.

Let be n the number of nodes and r the number of relations.
According to the implementation with Javascript a division is as expensive as a multiplication. But the calculation of a logarithm is 4 times more expensive then a multiplication or a division. The calculation time is:

(n * (1+1))² + r * (1 + 1) = 4*n² + 2*r

The complexity is O(n²) because the repulsive force is calculated among all nodes.
The force directed placement is better then the spring model because it fits better the criteria 3 about minimising edge crossing and has lower calculation complexity in calculating attractive forces. Force-directed placement strikes the spring model in performance issues too (criteria 1);

Local Minimum and Simulated Annealing

Both try to organise nodes and relations to minimise the energy of forces between nodes. The display results are the best, but is extremely expensive in the meaning of calculation complexity that is at least O(n²).
I implemented the algorithm of local minimum with minimising the energy state. The energy was calculated by the functions of the force-directed-graph. My experience with the local minimum is, that the nodes need lot more time to organise them self.
Simulated annealing is a very interesting concept. The difference between the this and other spring model based algorithm is, that you cool down the temperature (i.e., decrease ability of movement) on every step. You’ll get a stable system very fast depending on the amount of temperature decrease. The force-directed placement can be seen as a special version of simulated annealing, but without a temperature decrease. Depending on the implementation of simulated annealing, it is possible to get a runtime of O(n). Imagine a stable system with nodes. You add one with high kinetic energy. You only have to calculate the energies for the new nodes with all the other nodes. But doing this, you’ll get a bad organised system of nodes and relations.

Conclusion

I think the best graph drawing algorithm is a combination of the force-directed placement in combination with local minimum or simulated annealing. With the force-directed placement you get a good organised system in a short time. To reduce cpu time a change of algorithm is need, because it doesn’t make sense to move nodes only a little and calculate so much. I think local minimum or simulated annealing is a better choice for the calculation at the end because they are going to filter nodes from calculation. But all spring-embedded models aren’t scalable of cause the calculation time complexity of O(n²). We all have to live with it.