next up previous
Next: Layout Up: H3: Laying Out Large Previous: Introduction

Related Work


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.

2D Graph and Tree Drawing

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] gif. 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.

3D Graph Drawing

The 2 tex2htm_wrap_inline614 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.

3D Tree Drawing

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].

Focus+Context Techniques

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.

next up previous
Next: Layout Up: H3: Laying Out Large Previous: Introduction

Tamara Munzner Tue Jul 22 08:42:41 PDT 1997