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

This is an HTML description of our 5 bend, in O(n²) volume, graph drawing technique. It is related to the 6 bend Staircase layout and it is assumed the reader is familiar with this construct.

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. Here we present a layout scheme that draws any graph with n vertices of maximum degree 6, using at most 5 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 of vertices can be performed in O(n) time, while insertions/deletions of edges can be performed in O(1) time. Multiple edges and self loops are not permitted.

Note: In the 5 bend variant, self loops are not possible and insertions/deletions of vertices are O(n) time operations.

6 Bend Staircase
Home
Overview of Layout
Information on Isometric View
Top Routings
Bottom Routings
West Routings
East Routings
North Routings
South Routings
Underplane Routings

The 5 bend variant is similar to the 6 bend staircase model. It relies on pedestals, pillars and lanes, and also adds the notion of a climb which extends above the vertex. A series of planes under the layout is also introduced. Routings are always done from a lower vertex V to a higher vertex W (just as in the 6 bend variant).

side view of 6 bend staircase model side view of 5 bend staircase model
6 bend model side view. The vertices form a staircase and all routing is done below the staircase formed by the vertices.

Routings to the top port of W do go above the vertex but are limited to the region immediately surrounding the vertex. The region above the bounding boxes around the vertices is unused.

5 bend model side view. The vertices form a staircase as in the 6 bend model. However routing is now done both above and below the staircase formed by the vertices.
In the 6 bend staircase model all routing is done in the volume below the staircase formed by the vertices. The 5 bend variant uses both the volume above and below the staircase formed by the vertices for its routings.

As in the 6 bend variant the 5 bend model has a fixed number of planes (layers) associated with each vertex. These planes are used to separate the lanes from each vertex to ensure that no crossings can occur. The 5 bend model has 6 planes associated with each vertex: 4 in the vertex's neighbourhood, and 2 planes that are underplanes and are at a distance below the vertex that depends on the number of vertices in the graph. It is these underplanes that lead to the O(n) running times of insertions/deletions of vertices.

In the 5 bend model routing may occur in four regions: In the space immediately surrounding the vertex, in the space above the vertex V but at the plane level of W, in the space below W but at the plane level of V, and finally on the underplanes of any vertex V. These are detailed in the 5 bend layout page.

Lanes below the staircase route from one port to multiple ports. Lanes above the staircase route to one port from multiple ports.

Self loop image Self loops are not generally possible in the 5 bend variant of the staircase. This is due to ports on the opposite side of the vertex (North to South, West to East, Top to Bottom). It takes at least 4 bends for an edge to reach the opposite sides port. An inspection of possible routings shows that any 4 bend routing of this nature will possibly intersect internal routings, or pillars, lanes, and climbs. This leaves the possibility of a 5 bend routing but a 5 bend routing is impossible in this case. The argument is as follows: the ports on the opposite side of the vertex lie on the same plane (2 of them actually), and any 4 bend routing (which is the minimal routing to these opposite side ports) lies along one of these 2 possible planes. A fifth bend at any point will take us off this plane. If we use a bend to return to the plane we are one bend short of being able to reach the port. If we don't use a bend to return to the plane then we cannot enter the port on that plane.