Force Directed Graph Drawing
August 18, 2011 § Leave a comment
W. Tutte’s 1962 paper “How to Draw a Graph” proposes ‘Tutte’s algorithm, one of the first force directed methods to graph drawing. It was elegant, potentially efficient, though not always effective as nodes could overlap and have exponentially bad resolution.
Tutte’s algorithm is:
- Place some vertices in a circle.
- Place every other vertex at the barycentre of its neighbours.
Tutte’s exponentially bad resolution was demonstrated in this graph of the algorithm (weighted to process slower than normal) (coded as homework). It is also not useful for most networks, as they are seldom planar.
Algorithms should be
Hooke’s law takes the issue of resolution into account be repelling vertices that are not joined by an edge, instead of Tutte’s elastic bands, it is more like springs (which have a natural length, exterting a force that is | actualLength – naturalLength | ).
1. Apply Springs (Edges).
2. Apply Coulomb’s Law of electrical forces for non-edges (Repulsion). (Nodes).
3. Find minimum energy layout.
As the spring algorithm can be ineffective for large quantities of entities (for n ≥ 100’000). We can use a geometric clustering algorithm on top, with the simplest method being an oct/quad-tree. Clusters can be recursively computed, and be approximated to a centroid mass.
Other methods of handling scaling include the multi-dimensional scaling method (MDS) (Dimension Reduction) from statistics. One of these methods is PCA (Principle Component Analysis). The Fade Algorithm is also useful (forces on stars).
Reviewing different metro maps, both generated from human design and digitally, it has been observed that though digital generations can be better maps, this is no visual substitute for a human designer (perhaps due to the sacrifice of certain topologies).