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.
DIMACS Home Page