Lower Bounds for the Number of Bends in Three-Dimensional Orthogonal Graph Drawings
Wood, David R. (2001) Lower Bounds for the Number of Bends in Three-Dimensional Orthogonal Graph Drawings. In: Graph Drawing 8th International Symposium, GD 2000, September 20–23, 2000, Colonial Williamsburg, VA, USA , pp. 259-271 (Official URL: http://dx.doi.org/10.1007/3-540-44541-2_25).
Full text not available from this repository.
In this paper we present the first non-trivial lower bounds for the total number of bends in 3-D orthogonal drawings of maximum degree six graphs. In particular, we prove lower bounds for the number of bends in 3-D orthogonal drawings of complete simple graphs and multigraphs, which are tight in most cases. These result are used as the basis for the construction of infinite classes of c-connected simple graphs and multigraphs ($2\leq c\leq6$) of maximum degree $\Delta$ ($3\leq\Delta\leq6$) with lower bounds on the total number of bends for all members of the class. We also present lower bounds for the number of bends in general position 3-D orthogonal graph drawings. These results have significant ramifications for the `2-bends' problem, which is one of the most important open problems in the field.
Repository Staff Only: item control page