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.
Research supported in part by the ESPRIT LTR Project no. 20244 - ALCOM-IT and by the CNR Project “Geometria Computazionale Robusta con Applicazioni alla Grafica ed al CAD.”
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
H. Alt, M. Godau, and S. Whitesides. Universal 3-dimensional visibility representations for graphs, in[4], pp. 8–19.
T. C. Biedl. Heuristics for 3d-orthogonal graph drawings. In Proc. 4th Twente Workshop on Graphs and Combinatorial Optimization, pp. 41–44, 1995.
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.
F. J. Brandenburg, editor: Proceedings of Graph Drawing’ 95, Vol. 1027 of LNCS, Springer-Verlag, 1996.
I. Bruß and A. Frick. Fast interactive 3-D graph visualization, in[4], pp. 99–110.
T. Calamoneri and A. Sterbini. Drawing 2-, 3-, and 4-colorable graphs in O(n 2) volume, in [19], pp. 53–62.
R. F. Cohen, P. Eades, T. Lin, and F. Ruskey. Three-dimensional graph drawing. Algorithmica, 17(2):199–208, 1996.
I. F. Cruz and J. P. Twarog. 3d graph drawing with simulated annealing, in[4], pp. 162–165.
G. Di Battista, editor: Proceedings of Graph Drawing’ 97, Vol. 1353 of LNCS, Springer-Verlag, 1998.
D. Dodson. COMAIDE: Information visualization using cooperative 3D diagram layout, in[4], pp. 190–201.
P. Eades, C. Stirk, and S. Whitesides. The techniques of Kolmogorov and Bardzin for three dimensional orthogonal graph drawings. I. P. L., 60(2):97–103, 1987.
P. Eades, A. Symvonis, and S. Whitesides. Two algorithms for three dimensional orthogonal graph drawing, in[19], pp. 139–154.
S. P. Fekete, M. E. Houle, and S. Whitesides. New results on a visibility representation of graphs in 3-d, in [4] pp. 234–241.
A. Frick, C. Keskin, and V. Vogelmann. Integration of declarative approaches, in [19], pp. 184–192.
A. Garg, R. Tamassia, and P. Vocca. Drawing with colors. In Proc. 4th Annu. Europ. Sympos. Algorithms, vol. 1136 of LNCS, pp. 12–26. Springer-Verlag, 1996.
A. N. Kolmogorov and Y. M. Bardzin. About realization of sets in 3-dimensional space. Problems in Cybernetics, pp. 261–268, 1967.
G. Liotta and G. Di Battista. Computing proximity drawings of trees in the 3-dimensional space. In Proc. 4th Workshop Algorithms Data Struct., volume 955 of LNCS, pp. 239–250. Springer-Verlag, 1995.
B. Monien, F. Ramme, and H. Salmen. A parallel simulated annealing algorithm for generating 3D layouts of undirected graphs, in [4], pp. 396–408.
S. North, editor: Proceedings of Graph Drawing’ 96, Vol. 1190 of LNCS, Springer-Verlag, 1997.
D. I. Ostry. Some Three-Dimensional Graph Drawing Algorithms. M.Sc. thesis, Dept. Comput. Sci. and Soft. Eng., Univ. Newcastle, Oct. 1996.
J. Pach, T. Thiele, and G. Tóth. Three-dimensional grid drawings of graphs, in [9], pp. 47–51.
A. Papakostas and I. G. Tollis. Incremental orthogonal graph drawing in three dimensions, in[9], pp. 52–63.
M. Patrignani and M. Pizzonia The complexity of the matching-cut problem. Tech. Rep. RT-DIA-35-1998, Dept. of Computer Sci., Univ. di Roma Tre, 1998.
M. Patrignani and F. Vargiu. 3DCube: A tool for three dimensional graph drawing, in [9], pp. 284-290.
R. Webber and A. Scott. GOVE: Grammar-Oriented Visualisation Environment, in[4], pp. 516–519.
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.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Di Battista, G., Patrignani, M., Vargiu, F. (1998). A Split&Push Approach to 3D Orthogonal Drawing. In: Whitesides, S.H. (eds) Graph Drawing. GD 1998. Lecture Notes in Computer Science, vol 1547. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-37623-2_7
Download citation
DOI: https://doi.org/10.1007/3-540-37623-2_7
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65473-5
Online ISBN: 978-3-540-37623-1
eBook Packages: Springer Book Archive