Fully Dynamic 3-Dimensional Orthogonal Graph Drawing

Closson, M. and Gartshore, S. and Johansen, John and Wismath, Stephen (1999) Fully Dynamic 3-Dimensional Orthogonal Graph Drawing. In: Graph Drawing 7th International Symposium, GD’99, September 15-19, 1999, Štirín Castle, Czech Republic , pp. 49-58 (Official URL: http://dx.doi.org/10.1007/3-540-46648-7_5).

Full text not available from this repository.

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^{2}). 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 more elaborate construction that uses only 5 bends per edge, and a simpler, more balanced layout that requires at most 7 bends per edge are also described.

Item Type:Conference Paper
Additional Information:10.1007/3-540-46648-7_5
Classifications:M Methods > M.300 Dynamic / Incremental / Online
G Algorithms and Complexity > G.210 Bends
P Styles > P.600 Poly-line > P.600.700 Orthogonal
P Styles > P.060 3D
ID Code:238

Repository Staff Only: item control page

References

T. Biedl, Heuristics for 3D-Orthogonal Graph Drawings, Proceedings of the 4th Twente Workshop on Graphs and Combinatorial Optimization, Enshende, June 1995, pp. 41-44.

T. Biedl, T. Shermer, S. Whitesides, S. Wismath, Three-Dimensional Orthogonal Graph Drawing, Symposium on Graph Drawing 97, Lecture Notes in Computer Science 1353, Springer Verlag, 1998, pp. 76-86.

G. Di Battista, M. Patrignani, F. Vargiu, A Split & Push Approach to 3D Orthogonal Drawing, Symposium on Graph Drawing 98, Lecture Notes in Computer Science 1547, Springer Verlag, 1998. pp. 87-101.

P. Eades, A. Symvonis, S. Whitesides, Two Algorithms for Three-Dimensional Orthogonal Graph Drawing, Symposium on Graph Drawing 96, Lecture Notes in Computer Science 1190, Springer-Verlag, 1996, pp. 139-154.

A. Papakostas, I. Tollis, Algorithms for Incremental Orthogonal Graph Drawing in Three Dimensions, J. of Graph Algorithms and Applications, to appear.

D. Wood, An Algorithm for Three-Dimensional Orthogonal Graph Drawing, Symposium on Graph Drawing 98, Lecture Notes in Computer Science 1547, Springer Verlag, 1998. pp. 332-346.