1-Bend 3-D Orthogonal Box-Drawings: Two Open Problems Solved

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.