Logo

Login

An Algorithm for Three-Dimensional Orthogonal Graph Drawing

Wood, David R. (1998) An Algorithm for Three-Dimensional Orthogonal Graph Drawing. [Conference Paper]

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
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
Deposited By:Arnopolina, Galina
Deposited On:10 Nov 2004
Last Modified:18 Sep 2008 13:08
Alternative Locations:http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=1547&spage=332

Repository Staff Only: item control page

References

1. 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.

2. 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.

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

4. 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.

5. 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.

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

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

8. 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.

9. 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.

10. 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.

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

12. 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.

13. 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.

14. 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.

15. 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.

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

17. 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.

18. 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.

19. 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.

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

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

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

23. 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.

24. 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.

25. 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.

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.