Journal of Graph Algorithms and Applications
ISSN: 1526-1719

This web site is associated with a companion article published in the electronic Journal of Graph Algorithms and Applications, Special Issue on Graph Drawing '98 (GD '98). It features links to the actual animation, sample frames, and some additional material from the production process.

Ulrik Brandes, Vanessa K��b, Andres L�h, Dorothea Wagner and Thomas Willhalm:

Dynamic WWW Structures in 3D

Abstract: We describe a method for three-dimensional straight-line representation of dynamic directed graphs (such as parts of the World Wide Web). It has been developed on the occasion of the 1998 Graph Drawing Contest (see the contest report) and constitutes a customized blend of techniques known from the Graph Drawing literature. Since we feel that they may be of interest to others facing similar graph drawing problems, some technical details are mixed in.

Animation

WWW pages and links between them are conveniently described by means of a directed graph. Even though no particular structure of such a graph can be guaranteed, it typically contains tree-like hierachical substructures. One possible form of graphical representation is therefore, to display linked pages as boxes in space that are connected by straight line segments, where a referred box is placed below of the referring box.

Since the original file submitted to the Graph Drawing Contest is too big in file size (it was rendered at 640x480 pixels), we produced a smaller version in compressed format for download:

For a quick preview, click on thumbnails to see full size single frames (320x240 pixels, GIF, about 22 KBytes each).


Some Additional Data

The following data may be useful in reproducing our results or comprehending and customizing its production to a differnt setting.

  • The input data provided in the contest.
  • This simple 2D representation (format used for LEDA's graph editor GraphWin) was used to get acquainted with the graph. Black edges are inserted at some point in time, whereas red edges are inserted and later deleted again. Edge labels show insertion and deletion times, respectively. The relative insertion times of adjacent vertices is clockwise along that edge. The yellow node represents a broken link.
  • Dynamic layout quality was controlled using VRML output. Click on thumbnails to obtain VRML 1.0 source.

  • Before rendering edges as springs, this experiment (MPEG-1, 690 KBytes) was carried out.

    • Ulrik Brandes, Vanessa Kääb, Andres Löh, Dorothea Wagner and Thomas Willhalm: Dynamic WWW Structures in 3D. Journal of Graph Algorithms and Applications, Special Issue on Graph Drawing '98 (GD '98). This page was last modified May 18, 2000.