DIMACS TR: 2005-43
Interactive Navigation of Power-Law Graphs
Authors: James Abello and Frank van Ham
We illustrate how iterated deletion of vertices of degree one,
followed by biconnected graph decomposition constitute simple but
powerful preprocessing steps that we can use to create suitable
hierarchies on a graph. These hierarchies can then aid us
substantially in the process of graph layout and navigation. The
benefits of this approach are more apparent on sparse power-law
graphs when a hierarchy tree is computed for each biconnected
component via recursive clustering.
Our sample data sets include an Autonomous System-level Internet
topology with 11461 vertices and a 43,433 vertex graph detailing
the static call dependencies of the Linux core.
Paper Available at:
DIMACS Home Page