## Lower bounds for the number of bends in three-dimensional orthogonal graph drawings.(English)Zbl 1027.05094

Summary: This paper presents the first non-trivial lower bounds for the total number of bends in 3-D orthogonal graph drawings with vertices represented by points. 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 results are used as the basis for the construction of infinite classes of $$c$$-connected simple graphs, multigraphs, and pseudographs $$(2\leq c \leq 6$$) of maximum degree $$\Delta$$ $$(3 \leq \Delta \leq 6)$$, 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.

### MSC:

 05C85 Graph algorithms (graph-theoretic aspects) 05C10 Planar graphs; geometric and topological aspects of graph theory 05C35 Extremal problems in graph theory
Full Text: