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 , pp. 259-271(Official URL: http://dx.doi.org/10.1007/3-540-44541-2_25).

Full text not available from this repository.

Abstract

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.

Item Type: Conference Paper 10.1007/3-540-44541-2_25 M Methods > M.999 OthersZ Theory > Z.999 OthersP Styles > P.600 Poly-line > P.600.700 OrthogonalP Styles > P.060 3D http://gdea.informatik.uni-koeln.de/id/eprint/389