Lower Bounds for the Number of Bends in Three-Dimensional Orthogonal Graph Drawings

Wood, David R. (2001) Lower Bounds for the Number of Bends in Three-Dimensional Orthogonal Graph Drawings. In: Graph Drawing 8th International Symposium, GD 2000, September 20–23, 2000, Colonial Williamsburg, VA, USA , pp. 259-271 (Official URL: http://dx.doi.org/10.1007/3-540-44541-2_25).

Full text not available from this repository.

Abstract

In this paper we present the first non-trivial lower bounds for the total number of bends in 3-D orthogonal drawings of maximum degree six graphs. In particular, we prove lower bounds for the number of bends in 3-D orthogonal drawings of complete simple graphs and multigraphs, which are tight in most cases. These result are used as the basis for the construction of infinite classes of c-connected simple graphs and multigraphs ($2\leq c\leq6$) of maximum degree $\Delta$ ($3\leq\Delta\leq6$) with lower bounds on the total number of bends for all members of the class. We also present lower bounds for the number of bends in general position 3-D orthogonal graph drawings. These results have significant ramifications for the `2-bends' problem, which is one of the most important open problems in the field.

Item Type:Conference Paper
Additional Information:10.1007/3-540-44541-2_25
Classifications:M Methods > M.999 Others
Z Theory > Z.999 Others
P Styles > P.600 Poly-line > P.600.700 Orthogonal
P Styles > P.060 3D
ID Code:389

Repository Staff Only: item control page

References

T. C. Biedl. New lower bounds for orthogonal drawings. J. Graph Algorithms Appl., 2(7):1-31, 1998.

M. Closson, S. Gartshore, J. Johansen, and S. K. Wismath. Fully dynamic 3-dimensional orthogonal graph drawing. In J. Kratochvil, editor, Proc. Graph Drawing: 7th International Symp. (GD'99), volume 1731 of Lecture Notes in Comput. Sci., pages 49-58, Springer, 1999.

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

P. Eades, C. Stirk, and S. Whitesides. The techniques of Komolgorov and Bardzin 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.

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

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

M. Patrignani and F. Vargiu. 3DCube: a tool for 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.

R. Tamassia, I. G. Tollis, and J. S. Vitter. Lower bounds for planar orthogonal drawings of graphs. Inform. Process. Lett., 39(1):35-40, 1991.

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

D. R. Wood. On higher-dimensional orthogonal graph drawing. In J. Harland, editor, Proc. Computing: the Australasian Theory Symp. (CATS'97), volume 19(2) of Austral. Comput. Sci. Comm., pages 3-8, 1997.

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

D. R. Wood. Lower bounds for the number of bends in three-dimensional orthogonal graph drawings. Technical Report CS-AAG-2000-01, Basser Department of Computer Science, The University of Sydney, 2000.

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