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
Additional Information:	10.1007/3-540-44541-2_25
Classifications:	M Methods > M.999 Others Z Theory > Z.999 Others P Styles > P.600 Poly-line > P.600.700 Orthogonal P Styles > P.060 3D
URI:	http://gdea.informatik.uni-koeln.de/id/eprint/389

Actions (login required)

View Item