Cycles



next up previous
Next: Implementation Up: Layout Previous: Layout

Cycles

The Web is distributed resource which maintains a (very large) directed graph whose nodes are documents and whose edges are links between them (labelled by link relationships). Although it may provide a useful mental picture to think of a Weblet as tree hierarchy, most Weblets are not even directed acyclic graphs (DAGs), often containing many cycles due to ``backlinks''. Other common information hierarchies, such as a Unix filesystem with symbolic or hard links, also allow cycles.

Again hyperbolic geometry offers an elegant, systematic approach to visualizing directed graphs containing cycles. Just as trees can be nicely embedded in standard hyperbolic space (which contains no topologically significant loops), so too can directed graphs with cycles be nicely imbedded in hyperbolic manifolds-spaces which can wrap around and close up on themselves. Standing in such a space, you would be able to see many copies of yourself off in the distance, each image corresponding to one way that a light ray can loop back to you by following the wraparound topology of the space. The effect would be similar to a hall of mirrors, except that the images would never be right-left reversed. If there were a graph laid out in such a manifold, you would be able to see, receding into the distance, images of the current location which represent longer and longer chains of links leading back to that node. See [2] for more details on visualizing 3-manifolds from this ``insider's'' point of view.

However, due to the multiple images, sophisticated level-of-detail culling (beyond the abilities our first-generation software) is required to render the view inside a manifold efficiently. For this reason, we have initially taken an approach based on laying out an exhaustive subtree of the graph in standard hyperbolic space and then filling in the ``backlink'' edges (which will hopefully be as uniformly distributed as possible). The choice of an exhaustive subtree corresponds in more detail to choosing (1) a ``root node'', and (2) for each other node, one incoming edge as its ``main entry point''.

To see how to choose the entry points for best layout, consider first the (infinite) tree that would be obtained by navigating out from the root node, and attaching to each node copies of all its children, without regard to whether those children have already been seen and placed in the growing tree. This is similar to the manifold picture, but somewhat misleading as every node has multiple graphical representations, each variant missing all but one of the incoming edges. Figure 6, which shows such a layout, was made from the same data set as Figure 4. Nodes which are multiply represented are drawn in yellow.

 

Figure 6: No backlinks

WebOOGL [60KB] VRML [130KB] MPEG [200KB]

The required subtree can now be selected by choosing a traversal order for the above tree, and then only retaining the first copy of each graph node. The choice of traversal order has a major impact on the comprehensibility of the picture. Breadth-first search starting at the root node results in a more balanced, clearer picture than depth-first search. Compare Figures 7 and 8, which show the highly connected Weblet of an index of German cities.

 

Figure 7: Breadth-first search

WebOOGL [200KB] VRML [300KB] MPEG [200KB]

 

Figure 8: Depth-first search

WebOOGL [130KB] VRML [300KB] MPEG [1.02MB]



next up previous
Next: Implementation Up: Layout Previous: Layout



Tamara Munzner
Tue Nov 21 23:43:05 CST 1995