Three-Dimensional 1-Bend Graph Drawings
Pat Morin, David R. Wood · Journal of Graph Algorithms and Applications · 2004
We consider three-dimensional grid-drawings of graphs with at most one bend per edge. Under the additional requirement that the vertices be collinear, we prove that the minimum volume of such a drawing is (cn), where n is the number of vertices and c is the cutwidth of the graph. We then prove that every graph has a three-dimensional grid-drawing with O(n n) volume and one bend per edge. The best previous bound was O(n ).