A readable graph respects aesthetic criteria of syntatic validity, perceptual organization and aesthetic optimality as proposed by Kosak et al. in 1994. Some algorithms focus on minimizing edge crossing whilst other focus on other aesthetic criteria.
Spring-embedder 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 dependes 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 critera: Small number of edge crossing, optimal organization of vertices.

I’m evaluating the upper criterias for an implementation in Javascript. Javascript is highly sensible on calculation complexitiy. 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 calulated. 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.
Asuming n is the number of nodes and r is the number of relations.
According to the implementation with Javascript a division is as expensive as a multiplication. But the calulation 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 minimized edge crossing. The spring model does not. This algorithm is based constists of attractive repulsive forces among nods. As in the spring model, attractive forces f_a are calulated 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 fromt he number of nodes and the drawing area.

Asuming n is the number of nodes and r is the number of relations.
According to the implementation with Javascript a division is as expensive as a multiplication. But the calulation 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 critera 3 about minimizing edge crossing and has lower calculation complexitiy in calculating attractiv forces. Force-directed palcement strikes the spring model in performance issues too (criteria 1);

Local Minimum and Simulated Annealing

Both try to organize nodes and relations to minimize the energy of forces between nodes. The display results are the best, but is extremly expensive in the meaning of calculation complexity that is at least O(n²).
I implemented the algorithm of local minimum with minimizing 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 organize them self.
Simulated annealing is a very intersting concept. The difference between the this and other sprin 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 enery. You only have to calculate the energies for the new nodes with all the other nodes. But doing this, you’ll get a bad organized 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 organized 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.