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 , 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

Actions (login required)

View Item View Item