Smashing Peacocks Further: Drawing Quasi-Trees From Biconnected Components

Daniel Archambault, Tamara Munzner, and David Auber

Proceedings of InfoVis 2006. IEEE Transactions on Visualization and Computer Graphics 12(5):813--820
PDF | Abstract | Videos | Figures | Talk | Source Code

Paper

Abstract

Quasi-trees, namely graphs with tree-like structure, appear in many application domains, including bioinformatics and computer networks. Our new SPF approach exploits the structure of these graphs with a two-level approach to drawing, where the graph is decomposed into a tree of biconnected components. The low-level biconnected components are drawn with a force-directed approach that uses a spanning tree skeleton as a starting point for the layout. The higher-level structure of the graph is a true tree with meta-nodes of variable size that contain each biconnected component. That tree is drawn with a new area-aware variant of a tree drawing algorithm that handles high-degree nodes gracefully, at the cost of allowing edge-node overlaps. SPF performs an order of magnitude faster than the best previous approaches, while producing drawings of commensurate or improved quality.

Video

MPEG 4 Format
DivX Format

Figures


Talk

presentation PPT

Source Code

The
source code, including tulip libraries.