Extending the spring-electrical model to overcome warping effects

The spring-electrical model based force directed algorithm is widely used for drawing undirected graphs, and sophisticated implementations can be very efficient for visualizing large graphs. However, our practical experience shows that in many cases, layout quality suffers as a result of non-uniform vertex density. This gives rise to warping effects in that vertices on the outskirt of the drawing are often closer to each other than those near the center, and branches in a tree-like graph tend to cling together. In this paper we propose algorithms that overcome these effects. The algorithms combine the efficiency and good global structure of the spring-electrical model, with the flexibility of the Kamada-Kawai stress model of in specifying the ideal edge length, and are very effective in overcoming the warping effects.