Journal of Graph Algorithms and Applications
|Home||Issues||Aims and Scope||Instructions for Authors|
1-Bend 3-D Orthogonal Box-Drawings: Two Open Problems Solved
Vol. 5, no. 3, pp. 1-15, 2001. Regular paper.
Abstract 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 $K_n$ have volume $\Omega(n^3)$? (2) Is there a drawing of $K_n$ 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.
Submitted: May 2000.
Revised: November 2000.
Revised: March 2001.
Communicated by Giuseppe Liotta