Refinement of Three-Dimensional Orthogonal Graph Drawings

Lynn, Benjamin Y. S. and Symvonis, Antonios and Wood, David R. (2001) Refinement of Three-Dimensional Orthogonal Graph Drawings. In: Graph Drawing 8th International Symposium, GD 2000, September 20–23, 2000, Colonial Williamsburg, VA, USA , pp. 308-320 (Official URL: http://dx.doi.org/10.1007/3-540-44541-2_29).

Full text not available from this repository.

Abstract

In this paper we introduce a number of techniques for the refinement of three-dimensional orthogonal drawings of maximum degree six graphs. We have implemented several existing algorithms for three-dimensional orthogonal graph drawing including a number of heuristics to improve their performance. The performance of the refinements on the produced drawings is then evaluated in an extensive experimental study. We measure the aesthetic criteria of the bounding box volume, the average and maximum number of bends per edge, and the average and maximum edge length. On the same set of graphs used in Di Battista et al. [3], our main refinement algorithm improves the above aesthetic criteria by 80%, 38%, 10%, 54% and 49%, respectively.

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

Repository Staff Only: item control page

References

T. Biedl and T. Chan. Cross-coloring: improving the technique by Kolmogorov and Barzdin. Technical Report CS-2000-13, University of Waterloo, Canada, 2000.

M. Closson, S. Gartshore, J. Johansen, and S. K. Wismath. Fully dynamic 3-dimensional orthogonal graph drawing. In Kratochvil [8], pages 49-58.

G. Di Battista, M. Patrignani, and F. Vargiu. A split&push approach to 3D orthogonal drawing. In Whitesides [12], pages 87-101.

P. Eades, C. Stirk, and S. Whitesides. The techniques of Komolgorov and Bardizin for three dimensional orthogonal graph drawings. Inform. Proc. Lett., 60(2):97-103, 1996.

P. Eades, A. Symvonis, and S. Whitesides. Three dimensional orthogonal graph drawing algorithms. Discrete Applied Math., 103:55-87, 2000.

U. Fößmeier, C. Heß, and M. Kaufmann. On improving orthogonal drawings: the 4M-algorithm. In Whitesides [12], pages 125-137.

A. N. Kolmogorov and Ya. M. Barzdin. On the realization of nets in 3-dimensional space. Problems in Cybernetics, 8:261-268, March 1967.

J.Kratochvil, editor. Proc. Graph Drawing: 7th International Symp. (GD '99), volume 1731 of Lecture Notes in Computer Science, Springer, 1999.

A. Papakostas and I. G. Tollis. Algorithms for incremental orthogonal graph drawing in the three dimensions. J. Graph Algorithms Appl., 3(4):81-115, 1999.

M. Patrignani and F. Vargiu. 3DCube: a tool for the three dimensional graph drawing. In G. Di Battista, editor, Proc. Graph Drawing: 5th International Symp. (GD '97), volume 1353 of Lecture Notes in Comput. Sci., pages 284-290, Springer, 1998.

J. M. Six, K. G. Kakoulis, and I. G. Tollis. Refinement of orthogonal graph drawings. In Whitesides [12], pages 302-315.

S. Whitesides, editor. Proc. Graph Drawing: 6th International Symp. (GD'98), volume 1547 of Lecture Notes in Comput. Sci., Springer, 1998.

D. R. Wood. An algorithm for three-dimensional orthogonal graph drawing. In Whitesides [12], pages 332-346.

D. R. Wood. Three-Dimensional Orthogonal Graph Drawing. PhD thesis, School of Computer Science and Software Engineering, Monash University, Australia, 2000.