1-bend 3-D orthogonal box-drawings: Two open problems solved

This paper studies three-dimensional orthogonal box-drawings where edge-routes have at most one bend. Two open problems for such drawings are: (1) Does every drawing of Kn have volume Ω(n 3)? (2) Is there a drawing of Kn for which additionally the vertices are represented by cubes with surface O(n)? This paper answers both questions in the negative, and provides related results concerning volume bounds as well. Communicated by G. Liotta: submitted May 2000