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). In: Graph Drawing 6th International Symposium, GD’ 98, August 13-15, 1998, Montréal, Canada , pp. 87-101 (Official URL: http://dx.doi.org/10.1007/3-540-37623-2_7).

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
Additional Information:10.1007/3-540-37623-2_7
Classifications:M Methods > M.999 Others
P Styles > P.600 Poly-line > P.600.700 Orthogonal
P Styles > P.060 3D
ID Code:260

Repository Staff Only: item control page

References

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

T. Biedl. Heuristic 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 (Proc. GD '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²) 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 (Proc. GD '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, S. Whitesides. The Techniques of Kolmogorov and Barzdin for Three Dimensional Orthogonal Graph Drawing. 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. Fekete, M. Houle, and S.H. Whitesides. New results on a visibility representation of graphs in 3d. In [4], pages 234-241.

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

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.

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

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.

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 (Proc. GD '96), vol. 1190 of LNCS, Springer-Verlag, 1997.

D.I. Ostry. Some three dimensional graph drawing algorithms. M. Sc. thesis, Dept. Comp. Sci. and Soft. Eng., Univ. Newcastle, October 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], pages 52-63.

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.

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.