A good overview of the 3D information visualization literature can be found in Peter Young's survey paper [You96]. The most relevant areas related to the H3 layout technique are graph drawing and Focus+Context techniques.

The field of graph drawing has developed some effective solutions for
handling relatively small graphs. Traditional graph layout techniques
which work on general graphs are extremely effective for dozens of
nodes, can sometimes handle hundreds, and generally break down
completely for thousands of nodes. One relatively recent paper
[FLM94] characterized graphs as *tiny*, *small*, *
medium*, *large*, and *huge* respectively as having node
counts of 16, 32, 64, 128, and more than 128. These numbers may seem
surprisingly small to members of the visualization community, and
serve to illustrate the difficulty of finding an aesthetic layout of a
general graph. The extensive annotated bibliography of Battista et al
[BETT94] provides a good overview of the state of the field in
1994.

Several systems devoted to Web visualization draw on the techniques of graph drawing and use abstract node-link diagrams in two dimensions. The early Webmap system constructs a spanning tree of the documents visited in a browsing session, drawing both the spanning tree and non-tree links in two dimensions [Doe94]. The WebViz system for Web log analysis from Georgia Tech uses the expedient but crude approach of laying out the nodes randomly [PB94] . The MosaicG system, also from Georgia Tech, incorporates a 2D history browser into Mosaic itself [AS95]. Its features include two levels levels of detail (drawing nodes as document thumbnails or as simple boxes), subtree collapsing and expansion, and a more sophisticated ``tidy tree'' layout mechanism.

The 2 dimensional landscape of the SGI *fsn*
filesystem viewer [TS] employed a very concrete metaphor
where documents are represented as building-like structures which rise
above a ground plane. The Harmony Information Landscape
[APW96] extended this metaphor to more fully exploit 3D space
by showing hyperlink relationships between Web or Hyper-G documents
superimposed above and below the decorated plane.

Iterative force-directed placement systems model nodes and links as a mass-spring system, where nodes repulse each other but links exert an attractive force. The Gem3D system for general graphs [BF95] and the Hyper/Narcissus system for Web visualization [HDWB95] both use force-directed layout. While these iterative systems do well with relatively small graphs they have difficulty converging when the number of nodes scales from hundreds to thousands. The Narcissus constructs a graph based on the semantic content of documents. In contrast, we focus on the problem of graph layout and navigation for a given input graph rather than the problem of constructing that input graph. We do make use of domain-specific semantics, but only to to determine a spanning tree through an existing graph rather than to construct that graph from a set of nodes.

Although the H3 layout technique handles graphs, our methodology has
more in common with tree drawing methods than with drawing general
graphs. The cone tree system from Xerox PARC [RMC91]
introduced one of the most influential techniques in 3D tree drawing.
Carrière and Kazman [CK95] proposed a more sophisticated
bottom-up layout technique to minimize the chances that cone would
have overlapping territories. The *webviz* system extended cone
trees from euclidean to hyperbolic space [MB95].

Methods of introducing deliberate distortion in order to show a large amount of contextual information in a given amount of screen area are collectively known as Focus+Context views. Some papers, including the original cone tree paper [RMC91], advocate using 3D euclidean perspective to achieve this goal. A more aggressive approach is to view a graph through a fisheye lens [SB94, KRB94], or drawn on a stretchable rubber sheet [SSTR93, SCCF95]. Taxonomies by Noik [Noi94] and Leung and Apperley [LA94] present a useful analysis of Focus+Context techniques, which we will not duplicate here. Noik in particular discusses Focus+Context techniques as they relate to graph drawing. The H3 method is more similar to single-focus fisheye techniques than to the multiple-focus rubber sheet methods. In Section 4 we discuss in depth the advantages of hyperbolic layout over fisheye lens techniques.

The fractal tree work of Koike and Yoshimara [KY93] is similar in spirit to hyperbolic approaches. Both tame the exponential explosion of tree nodes by drawing trees in a mathematical space with nonstandard properties - dimension or distance, respectively. While the fractal tree work was an intriguing beginning and included a 3D view, their system did not tackle the 3D layout problems of ensuring that subtrees do not overlap in space.

The first hyperbolic visualization system described in the information
visualization literature was the 2D hyperbolic tree browser from Xerox
PARC [LR94]. The *webviz* hyperbolic browser from the
Geometry Center [MB95] handled general graphs in 3D. The
*webviz* layout algorithm did not exploit 3D hyperbolic space to
its full potential: the amount of displayed information compared to
the amount of white space was quite sparse. Moreover, the *webviz*
system drew all links in the graph at all times, so highly connected
graphs were quite cluttered.