TY - JOUR
AU - Morin, Pat
AU - Wood, David
PY - 2004/01/01
Y2 - 2024/06/13
TI - Three-Dimensional 1-Bend Graph Drawings
JF - Journal of Graph Algorithms and Applications
JA - JGAA
VL - 8
IS - 3
SE -
DO - 10.7155/jgaa.00095
UR - https://jgaa.info/index.php/jgaa/article/view/paper95
SP - 357-366
AB - 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 Θ(<i>cn</i>), where <i>n</i> is the number of vertices and <i>c</i> is the cutwidth of the graph. We then prove that every graph has a three-dimensional grid-drawing with <i>O</i>(<i>n</i><sup>3</sup>/log<sup>2</sup> <i>n</i>) volume and one bend per edge. The best previous bound was <i>O</i>(<i>n</i><sup>3</sup>).<div class="p"><!----></div>
ER -