Fully Dynamic 3-Dimensional Orthogonal Graph Drawing
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.
Abstract:
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.
|
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.
|
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 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.
