[an error occurred while processing this directive] H3: Laying Out Large Directed Graphs in 3D Hyperbolic Space

H3: Laying Out Large Directed Graphs in 3D Hyperbolic Space

Tamara Munzner

Proceedings of the 1997 IEEE Symposium on Information Visualization, October 20-21 1997, Phoenix, AZ, pp 2-10, 1997.


We present the H3 layout technique for drawing large directed graphs as node-link diagrams in 3D hyperbolic space. We can lay out much larger structures than can be handled using traditional techniques for drawing general graphs because we assume a hierarchical nature of the data. We impose a hierarchy on the graph by using domain-specific knowledge to find an appropriate spanning tree. Links which are not part of the spanning tree do not influence the layout but can be selectively drawn by user request.

The volume of hyperbolic 3-space increases exponentially, as opposed to the familiar geometric increase of euclidean 3-space. We exploit this exponential amount of room by computing the layout according to the hyperbolic metric. We optimize the cone tree layout algorithm for 3D hyperbolic space by placing children on a hemisphere around the cone mouth instead of on its perimeter. Hyperbolic navigation affords a Focus+Context view of the structure with minimal visual clutter. We have successfully laid out hierarchies of over 20,000 nodes. Our implementation accommodates navigation through graphs too large to be rendered interactively by allowing the user to explicitly prune or expand subtrees.

Additional information

Site Manager
An implementation of the system described in the paper is included in this free web publishing package from SGI.
H3/H3Viewer libraries
available for free noncommercial use
H3 Video

Versions of the paper:

Related papers:

Color Figures:

High Resolution TIFF Color Figures:

1, 2a, 2b, 4a, 4b, 4c, 4d, 4e, 4f, 4g, 4h, 4i, Plate1a, Plate1b, Plate1c, Plate2a, Plate2b

Please request permission before reprinting figures.

IEEE Copyright Notice
Last modified: Fri Jun 8 15:33:46 PDT 2001