Three-Dimensional Orthogonal Graph Drawing with Optimal Volume

Biedl, Therese and Thiele, Torsten and Wood, David R. (2001) Three-Dimensional Orthogonal Graph Drawing with Optimal Volume. In: Graph Drawing 8th International Symposium, GD 2000, September 20–23, 2000, Colonial Williamsburg, VA, USA , pp. 284-295 (Official URL: http://dx.doi.org/10.1007/3-540-44541-2_27).

Full text not available from this repository.

Abstract

In this paper, we study three-dimensional orthogonal box-drawings of graphs without loops. We provide lower bounds for three scenarios: (1) drawings where vertices have bounded aspect ratio, (2) drawings where the surface of vertices is proportional to their degree, and (3) drawings without any such restrictions. Then we give constructions that match the lower bounds in all scenarios within an order of magnitude.

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

Repository Staff Only: item control page

References

A. Aggarwal, M. Klawe, and P. Shor. Multilayer grid embeddings for VLSI. Algorithmica, 6(1):129-151, 1991.

N. Alon and J. Spencer. The Probabilistic Method. John Wiley & Sons, 1992.

T. Biedl. Three approaches to 3D-orthogonal box-drawings. In Whitesides [17], pages 30-43.

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

T. Biedl, T. Shermer, S. Whitesides, and S. Wismath. Bounds for orthogonal 3-D graph drawing. J. Graph Alg. Appl., 3(4):63-79, 1999.

T. Biedl, T. Thiele and D. R. Wood. Three-Dimensional Orthogonal Graph Drawing with Optimal Volume. Technical Report CS-2000-12. Department of Computer Science, University of Waterloo, Canada, 2000.

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

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

P. Eades, C. Stirk, and S. Whitesides. The techniques of Kolmogorov and Bardzin for three-dimensional orthogonal graph drawings. Information Processing Letters, 60(2):97-103, 1996.

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

É. K. Fogel. An elementary proof of formulae of de la Vallée Poussin (In Russian). Latvijas PSR Zinatnu Akad. Vestis, 11(40):123-130, 1950.

K. Hagihara, N. Tokura, and N. Suzuki. Graph embedding on a three-dimensional model. Systems-Comput.-Controls, 14(6):58-66, 1983.

D. Kleitman and M. Krieger. An optimal bound for two dimensional bin packing. In 16th Annual Symposium on Foundations of Computer Science (FOCS'75), pages 163-168. IEEE, 1975.

J. Kratochvíl, editor. Symposium on Graph Drawing 99, volume 1731 of Lecture Notes in Computer Science. Springer-Verlag, 1999.

A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs. Combinatorica, 8:261-277, 1988.

A. Papakostas and I. Tollis. Incremental orthogonal graph drawing in three dimensions. J. Graph Alg. Appl., 3(4):81-115, 1999.

S. Whitesides, editor. Symposium on Graph Drawing 98, volume 1547 of Lecture Notes in Computer Science. Springer-Verlag 1998.

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

D. R. Wood. Multi-dimensional orthogonal graph drawing with small boxes. In Kratochvíl [14], pages 311-322.

D. R. Wood. A new algorithm and open problems in three-dimensional and orthogonal graph drawing. In R. Raman and J. Simpson, editors, Proc. Australasian Workshop on Combinatorial Algorithms (AWOCA '99), pages 157-167. Curtin University of Technology, Perth, 1999.