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

This paper studies three-dimensional drawings of graphs where vertices are represented by axis-parallel boxes and edges are represented by disjoint routes with at most one bend in a three-dimensional rectangular grid. It is known that such box-drawings without bends are not always possible. The two open problems on these 1-bend box-drawings which are solved in the paper are the following: (1) Does every 1-bend drawing of \(K_n\) have volume \(\Omega(n^3)\)? (2) Is there a 1-bend drawing of \(K_n\) where in addition the vertices are represented by cubes with surface \(O(n)\)? The paper answers both questions in the negative and provides other results for 1-bend drawings of graphs without loops and multiple edges. Furthermore, other bounds are obtained for 1-bend drawings of the Ramanujan graph.