Logo

Login | Create Account

A Split&Push Approach to 3D Orthogonal Drawing (Extended Abstract)

Di Battista, Giuseppe and Patrignani, Maurizio and Vargiu, Francesco (1998) A Split&Push Approach to 3D Orthogonal Drawing (Extended Abstract). [Conference Paper]

Full text not available from this repository.

Abstract

We present a method for constructing orthogonal drawings of graphs of maximum degree six in three dimensions. Such a method is based on generating the final drawing through a sequence of steps, starting from a “degenerate” drawing. At each step the drawing “splits” into two pieces and finds a structure more similar to its final version. Also, we test the effectiveness of our approach by performing an experimental comparison with several existing algorithms.

Item Type:Conference Paper
Classifications:M Methods > M.999 Others
P Styles > P.600 Poly-line > P.600.700 Orthogonal
P Styles > P.060 3D
ID Code:260
Deposited By:Arnopolina, Galina
Deposited On:09 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=87

Repository Staff Only: item control page

References

1. H. Alt, M. Godau, and S.H. Whitesides. Universal 3-dimensional visibility representations for graphs. In [4] pages 8-19.

2. T. Biedl. Heuristic for 3d-orthogonal graph drawings. In Proc. 4th Twente Workshop on Graphs and Combinatorial Optimization, pp. 41-44, 1995.

3. p. Bose, H. Everett, S.P. Fekete, A. Lubiw, H. Meijer, K. Romanik, T. Shermer, and S. Whitesides. On a visibility representation for graphs in three dimensions. In D. Avis and P. Bose, eds., Snapshots in Computational and Discrete Geometry, Vol. III, pp. 2-25. McGill Univ., July 1994. McGill tech. Rep. SOCS-94.50.

4. F. J. Brandenburg, editor: Proceedings of Graph Drawing '95 (Proc. GD '95), vol. 1027 of LNCS, Springer-Verlag, 1996.

5. I. Bruß and A. Frick. Fast interactive 3-d graph visualization. In [4], pp. 99-110.

6. T. Calamoneri and A. Sterbini. Drawing 2-,3-, and 4-colorable graphs in O(n²) volume. In [19], pp. 53-62.

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

8. I.F. Cruz and J.P. Twarog. 3d graph drawing with simulated annealing. In [4], pp. 162-165.

9. G. Di Battista, editor: Proceedings of Graph Drawing '97 (Proc. GD '97), vol. 1353 of LNCS, Springer-Verlag, 1998.

10. D. Dodson. Comaide: Information visualization using cooperative 3d diagram layout. In [4], pp. 190-201.

11. P. Eades, C. Stirk, S. Whitesides. The Techniques of Kolmogorov and Barzdin for Three Dimensional Orthogonal Graph Drawing. I.P.L., 60(2):97-103, 1987.

12. P. Eades, A. Symvonis, and S. Whitesides. Two Algorithms for Three Dimensional Orthogonal Graph Drawing. In [19], pp. 139-154.

13. S. Fekete, M. Houle, and S.H. Whitesides. New results on a visibility representation of graphs in 3d. In [4], pages 234-241.

14. A. Frick, C. Keskin, and V. Vogelmann. Integration of declarative approaches. In [19], pages 184-192.

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

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. G. Liotta and G. Di Battista. Computing proximity drawings of trees in the 3-dimensional space. In Proc. 4th Workshop Algorithms and Data Structures, vol. 955 of LNCS, pp. 239-250. Springer-Verlag, 1995.

18. B. Monien, F. Ramme, and H. Salmen. A parallel simulated annealing algorithm for generating 3D layouts of undirected graphs. In [4], pp. 396-408.

19. S. North, editor: Proceedings of Graph Drawing '96 (Proc. GD '96), vol. 1190 of LNCS, Springer-Verlag, 1997.

20. D.I. Ostry. Some three dimensional graph drawing algorithms. M. Sc. thesis, Dept. Comp. Sci. and Soft. Eng., Univ. Newcastle, October 1996.

21. J. Pach, T. Thiele, and G. Tóth. Three-dimensional grid drawings of graphs. In [9], pp. 47-51.

22. A. Papakostas and I.G. Tollis. Incremental orthogonal graph drawing in three dimensions. In [9], pages 52-63.

23. M. Patrignani and M. Pizzonia. The complexity of the matching-cut problem. Tech. Report RT-DIA-35-1998. Dept. of Comp. Sci., Univ. di Roma Tre, 1998.

24. M. Patrignani and F. Vargiu. 3DCube: A tool for three dimensional graph drawing. In [9], pp. 284-290.

25. R. Webber and A. Scott. GOVE: Grammar-oriented Visualisation Environment. In [4], pp. 516-519.

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

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.