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:

  1. Place some vertices in a circle.
  2. Place every other vertex at the barycentre of its neighbours.
It is essentially equivalent to a minimisation algorithm.
.

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

  • EFFECTIVE
  • EFFICIENT
  • ELEGANT

.

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).

.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

What’s this?

You are currently reading Force Directed Graph Drawing at DECO } Han.

meta