Fully Dynamic 3-Dimensional Orthogonal Graph Drawing

M. Closson S. Gartshore J. Johansen
S.K. Wismath

Department of Mathematics and Computer Science,

University of Lethbridge,

Lethbridge, Alberta, T1K-3M4, Canada

A preliminary version of this research was recently presented at Graph Drawing 99 - September 15-19 in Prague.


In a 3-dimensional orthogonal drawing of a graph, vertices are mapped to grid points on an integer lattice and edges are routed along integer grid lines. In this paper, we present a layout scheme that draws any graph with n vertices of maximum degree 6, using at most 6 bends per edge and in a volume of O(n²). The advantage of our strategy over other drawing methods is that our method is fully dynamic, allowing both insertion and deletion of vertices and edges, while maintaining the volume and bend bounds. The drawing can be obtained in O(n) time and insertions/deletions can be performed in O(1) time. Multiple edges and self loops are permitted.

A VRML screen shot

VRML demos - Some VRML worlds showing some example layouts using the Dynamic 3-Dimensional Orthogonal Graph Drawing algorithm. These worlds were created using the OrthoPak package which is available from the U. of Lethbridge, for drawing graphs orthogonally in 3-dimensions.

2 vertex demo This VRML demo shows 2 vertices that are joined by two edges. The layers and pedestals of each vertex are shown as transparent.

K7 demo This is an example of the complete graph on 7 vertices.

Multi demo This is an example showing some multiple edges.

Multi 2 demo This is an example world showing multiple edges and self loops.

Animated K7

Five Bend Layout

A related 5 bend construction has also been developed. Supplementary pictures and description of this layout is available: 5 BEND.

Animations and pictures:

A compressed ANIMATION (5M) that demonstrates a particular edge routing in our staircase drawing can be viewed.

In the paper, we also describe an orthogonal spiral construction. A gzipped animation following a routing of the related spiral routing algorithm is also available Spiral video.

A small photogallery of various graphs using different layouts is also available.

The animations were created using the ray tracing package povray. The VRML viewing program VRWave is the viewing package we used to view these worlds.

The layers and pedestals of a vertex

The above screenshot shows a single vertex with its pedestals reaching to their respective layers. Below is a small graph drawn in black with the lanes, pillars, and layers also displayed.

The pillars, lanes, and layers of a small graph