×

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
PDF BibTeX XML Cite
Full Text: DOI EuDML