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

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