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.

My student project about Metadata-Management at the Zürcher Kantonalbank (ZKB) was a big success. The goals were to implement a prototype of an easy-to-use application for browsing, searching and navigating through meta data, defining processes how people have to updated and import meta data, defining a data model where meta data of every business area can inserted and to evaluate some more questions.
I invented a new type of visualization for meta data of an operational datat store or Data-Warehouse.
Well, people were quite impressed being presented such a visualization, that abstracts from technical elements and elements from the business areas. With the developed browser you can see the relations between technical elements and elements from the business area. With this prototype it’s easy to make a complete impact analysis, making reports, see how elements are related to each other, and so on.
Unfortunately I can’t publish a screenshot of the prototype or go more deeper into details because the results of my student project is only for ZKB’s internal.

The duration of this student project was 12 weeks. In this time a met a lot of friendly and competent people at the ZKB. They all were nicely and friendly. I feel sadly to stop working there, but I have to finish my study and write my diploma thesis about an Implementation of a Graph Based Knowledge Browser for a CMS. With this implementation it is possible to measure the amount of knowledge transfer from one company to another e.g. in a outsourcing process.
In this student project I learned a lot of the factor humans. At the university you learn to solve problems and invent and innovate new solutions. But the focus is set to the solution. But in the real life, you have to make people understand your solution, sensibilize people for the problem and the need for a solution. It’s not a problem, it’s a challenge!
I wrote quite a lot source code and documentation. Just to imagine how much I wrote in 12 Weeks, I’ll list them all:

• over 14′000 lines of code
• 119 pages of program documentation
• 29 pages of user documentation
• 25 pages of data model descriptions (tables, attributes)
• 61 pages for the final paper
• 11 presentations in different business areas of the banc

I can recommend the ZKB to everyone making a studyproject there. It’s a good company with very nice people.