Biedl, Therese

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

J. Graph Algorithms Appl. 5(3), 15 p. (2001)


Summary: 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 $\Omega (n3)$? (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; revised November 2000 and March 2001.Research partially supported by NSERC. The results in this paper were presented at the 12th Canadian Conference on Computational Geometry, August 2000.