Orthogonal 3-D Graph Drawing

Biedl, Therese and Shermer, Thomas and Whitesides, Sue and Wismath, Stephen (1998) Orthogonal 3-D Graph Drawing. In: Graph Drawing 5th International Symposium, GD '97, September 18-20, 1997 , pp. 76-86(Official URL: http://dx.doi.org/10.1007/3-540-63938-1_52).

Full text not available from this repository.


This paper studies 3-D orthogonal grid drawings for graphs of arbitrary degree, K_{n} in particular, with vertices drawn as boxes. It establishes an asymptotic lower bound for the volume of the bounding box of such drawings and exhibits a construction that achieves this bound. No edge route in this unconstrained construction bends more than three times. For drawings constrained to have at most k bends on any edge route, simple constructions are given for k=1 and k=2. The unconstrained construction handles the k \geq 3 cases, while for k=0 (no bends), it is proved here that not all graphs can be drawn.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-63938-1_52
Classifications: G Algorithms and Complexity > G.210 Bends
P Styles > P.600 Poly-line > P.600.700 Orthogonal
P Styles > P.060 3D
URI: http://gdea.informatik.uni-koeln.de/id/eprint/176

Actions (login required)

View Item View Item