An Algorithm for Three-Dimensional Orthogonal Graph Drawing

Wood, David R. (1998) An Algorithm for Three-Dimensional Orthogonal Graph Drawing. In: Graph Drawing 6th International Symposium, GD’ 98, August 13-15, 1998, Montréal, Canada , pp. 332-346 (Official URL: http://dx.doi.org/10.1007/3-540-37623-2_25).

Full text not available from this repository.

Abstract

In this paper we present an algorithm for 3-dimensional orthogonal graph drawing based on the movement of vertices from an initial layout along the main diagonal of a cube. For an n-vertex m-edge graph with maximum degree six, the algorithm produces drawings with bounding box volume at most 2.37n^3 and with a total of 7m/3 bends, using no more than 4 bends per edge route. For maximum degree five graphs the bounding box has volume n^3 and each edge route has two bends. These results establish new bounds for 3-dimensional orthogonal graph drawing algorithms and improve on some existing bounds.

Item Type:Conference Paper
Additional Information:10.1007/3-540-37623-2_25
Classifications:G Algorithms and Complexity > G.070 Area / Edge Length
G Algorithms and Complexity > G.210 Bends
P Styles > P.600 Poly-line > P.600.700 Orthogonal
P Styles > P.060 3D
P Styles > P.999 Others
ID Code:337

Repository Staff Only: item control page

References

H. Alt, M. Godau, and S.H. Whitesides. Universal 3-dimensional visibility representations for graphs. In Graph Drawing (Proc. GD '95), vol. 1027 of LNCS, pages 8-19. Springer-Verlag, 1996.

T. Biedl, T. Shermer, S. Whitesides, and S. Wismath. Orthogonal 3-D graph drawing. In DiBattista, editor, Symposium on Graph Drawing 97, vol. 1353 of LNCS. Springer-Verlag, 1998, pages 76-86.

R.L. Brooks. On colouring the nodes of a network. Proc. Cambridge Philos. Soc., 37:194-197, 1941.

T. Calamoneri and A. Massini. On three dimensional layout of interconnection networks. In Proc. 5th Int. Symp. Graph drawing (Rome), LNCS 1353:64-75, Springer-Verlag, 1997.

M. Chrobak, M.T. Goodrich, and R. Tamassia. Convex drawings of graphs in two and three dimensions. In Proc. 12th Annu. ACM Sympos. Comput. Geom., pages 319-328, 1996.

R.F. Cohen, P. Eades, T. Lin, and F. Ruskey. Three-dimensional graph drawing. Algorithmica, 17(2):199-208, 1996.

Peter Eades and Qing-Wen Feng. Multilevel Visualization of Clustered Graphs. LNCS, 1190:101-112, 1997.

P. Eades and P. Garvan. Drawing stressed planar graphs in three dimensions. In Graph Drawing (Proc. GD '95), vol. 1027 of LNCS, pages 212-223, Springer-Verlag, 1996.

P. Eades, C. Stirk, S. Whitesides. The Techniques of Kolmogorov and Barzdin for Three Dimensional Orthogonal Graph Drawing. Information Processing Lett., 60(2):97-103, 1996.

P. Eades, A. Symvonis, and S. Whitesides. Two Algorithms for Three Dimensional Orthogonal Graph Drawing. In Proc. of the Symp. on Graph Drawing, GD'96, pages 139-154. Springer Verlag, September 1996.

P. Eades, A. Symvonis, and S. Whitesides. Three Dimensional Orthogonal Graph Drawing Algorithms. 1998, submitted.

S. Fekete, M. Houle, and S.H. Whitesides. New results on a visibility representation of graphs in 3d. In Graph Drawing (Proc. GD '95), vol. 1027 of LNCS, pages 234-241, Springer-Verlag, 1996.

A. Garg, R. Tamassia, and P. Vocca. Drawing with colors. In Pco. 4th Annu. European Symp. Algorithms (ESA '96),vol. 1136 of LNCS, pp. 12-26, Springer-Verlag, 1996.

P. Garvan. Drawing and labeling graphs in three dimensions. In M. Patel, editor, Proc. 20th Australian Comput. Science Conference (ACSC '97), vol. 19(1) of Australian Comput. Sci. Comms., pages 83-91, Macquarie University, 1997.

H. Koike. An application of three-dimensional visualization to object-oriented programming. In Proc. Advanced Visual Interfaces (AVI '92), vol. 36 of World Scientific Series in Comput. Sci., pages 180-192, 1992.

A.N. Kolmogorov and Ya.M. Brazdin. About realisation of sets in 3-dimensional space. Problems in Cybernetics. March 1967, pages 261-268.

J. Pach, T. Thiele, and G. Tóth. Three-dimensional grid drawings of graphs. In G. Di Battista, editor: Proceedings of Graph Drawing '97 (Proc. GD '97), vol. 1353 of LNCS, pp. 47-51. Springer-Verlag, 1998.

A. Papakostas and I.G. Tollis. Incremental orthogonal graph drawing in three dimensions. In DiBattista, editor: Proceedings of Graph Drawing '97 (Proc. GD '97), vol. 1353 of LNCS, pages 52-63. Springer-Verlag, 1998.

M. Patrignani and F. Vargiu. 3DCube: A tool for three dimensional graph drawing. In DiBattista, editor: Proceedings of Graph Drawing '97 (Proc. GD '97), vol. 1353 of LNCS, pages 284-290. Springer-Verlag, 1998.

Franco P. Preparata. Optimal three-dimensional VLSI layouts. Mathematical Systems Theorie, vol. 16, 1983, pages 1-8.

S.P. Reiss. 3-D visualization of program information. Graph Drawing (Proc. GD '94), LNCS, 894, Springer-Verlag, pages 12-24, 1995.

A.L. Rosenberg. Three-Dimensional VLSI: A case Study. Journal of the ACM, vol. 30(3), pages 397-416, 1983.

David Wood. On Higher-Dimensional Orthogonal Graph

Drawing. In J. Harland, editor, Proc. Computing: the Australian Theory Symp. (CATS '97), vol. 19(2) of Australian Comput. Sci. Comms., pages 3-8. Macquarie University, 1997.

D.R. Wood. Towards a 2-bends algorithm for three-dimensional orthogonal graph drawing. In V. Estivill-Castro, editor, Proc. Australian Workshop on combinatorial algorithms (AWOCA '97), pages 102-107. Queensland University of Technology, 1997.

D.R. Wood. Two-bend three-dimensional orthogonal grid drawing of maximum degree five graphs. Technical report, School of computer Science and Software Engineering, Monash University, 1998. available at ftp.csse.monash.edu.au.