Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00095
Three-Dimensional 1-Bend Graph Drawings
Vol. 8, no. 3, pp. 357-366, 2004. Concise paper.
Abstract 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(n3/log2
n) volume and one bend per edge. The best previous bound was O(n3).
|
Journal Supporters
|