|M. Closson||S. Gartshore||J. Johansen|
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.
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.
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).
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.