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: http://dx.doi.org/10.1007/3-540-37623-2_3).

Full text not available from this repository.

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.

Item Type: Conference Paper 10.1007/3-540-37623-2_3 M Methods > M.999 OthersG Algorithms and Complexity > G.999 OthersP Styles > P.600 Poly-line > P.600.700 OrthogonalP Styles > P.060 3D http://gdea.informatik.uni-koeln.de/id/eprint/205