Three Approaches to 3D-Orthogonal Box-Drawings (Extended Abstract)

Biedl, Therese (1998) Three Approaches to 3D-Orthogonal Box-Drawings (Extended Abstract). In: Graph Drawing 6th International Symposium, GD’ 98, August 13-15, 1998, Montréal, Canada , pp. 30-43 (Official URL:

Full text not available from this repository.


In this paper, we study orthogonal graph drawings in three dimensions with nodes drawn as boxes. The algorithms that we present can be differentiated as resulting from three different approaches to creating 3D-drawings; we call these approaches edge-lifting, half-edge-lifting, and three-phase-method. Let G be a graph with n vertices, m edges, and maximum degree \Delta. We obtain a drawing of G in an n \times n \times \Delta-grid where the surface area of the box of a node v is O(deg(v)); this improves significantly on previous results. We also consider drawings with at most one node per grid-plane, and exhibit constructions in an n \times n \times m-grid and a lower bound of \Omega (m²); hence upper and lower bounds match for graphs with \Theta (n²) edges.

Item Type:Conference Paper
Additional Information:10.1007/3-540-37623-2_3
Classifications:M Methods > M.999 Others
G Algorithms and Complexity > G.999 Others
P Styles > P.600 Poly-line > P.600.700 Orthogonal
P Styles > P.060 3D
ID Code:205

Repository Staff Only: item control page


T. Biedl and G. Kant. A Better Heuristic for Orthogonal Graph Drawings. Comput. Geom. Theory Appl., 9:159-180, 1998.

T. Biedl and M. Kaufmann. Area-efficient static and incremental graph drawings. In 5th European Symposium on Algorithms, vol. 1284 of LNCS, pages 37-52. Springer-Verlag, 1997.

T. Biedl, B. Madden, and I.G. Tollis. The three-phase method: A unified approach to orthogonal graph drawing. In DiBattista [7], pages 391-402.

T. Biedl, T. Shermer, S. Whitesides, and S. Wismath. Orthogonal 3-D graph drawing. In DiBattista [7], pages 76-86.

G. Di Battista, P. Eades, R. Tamassia, and I.G. Tollis. Algorithms for drawing graphs: An annotated bibliography. Comput. Geom. Theory Appl., 4:235-282, 1994.

G. Di Battista, A. Garg, G. Liotta, R. Tamassia, E. Tassinari, and F. Vargiu. An experimental comparison of three graph drawing algorithms. Comput. Geom. Theor. Appl., 7(5-6), 1997.

G. DiBattista, editor. Symposium on Graph Drawing 97, vol. 1353 of LNCS. Springer-Verlag, 1998.

P. Eades, A. Symvonis, and S. Whitesides. Two Algorithms for Three Dimensional Orthogonal Graph Drawing. In S. North, editor, Symposium on Graph Drawing 96, vol. 1190 of LNCS. Springer-Verlag, 1997, pp. 139-154.

U. Fößmeier and M. Kaufmann. Drawing high degree graphs with low bend numbers. In F. Brandenburg, editor, Symposium on Graph Drawing 95, vol. 1027 of LNCS. Springer-Verlag, 1996, pp. 254-266.

U. Fößmeier and M. Kaufmann. Algorithms and area bounds for nonplanar orthogonal drawings. In DiBattista [7], pages 134-145.

A. Papakostas and I.G. Tollis. High-degree orthogonal drawings with small grid-size and few bends. In 5th Workshop on Algorithms and Data Structures, vol. 1272 of LNCS, pages 354-367. Springer-Verlag, 1997.

A. Papakostas and I.G. Tollis. Algorithms for Area-Efficient Orthogonal Drawings. Comput. Geom. Theory Appl., 9:83-110, 1998.

A. Papakostas and I.G. Tollis. Incremental orthogonal graph drawing in three dimensions. In DiBattista [7], pages 52-63.

A.L. Rosenberg. Three-Dimensional VLSI: A case Study. Journal of the ACM, vol. 30(3), pages 397-416, 1983.

R. Tamassia. On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput. 16 (1987), pages 421-444.