Lower bounds for the number of bends in three-dimensional orthogonal graph drawings

Research output: Chapter in Book/Report/Conference proceedingChapter (Book)Researchpeer-review

Abstract

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 result are used as the basis for the construction of infinite classes of c-connected simple graphs, multigraphs, and pseudographs (2 < c < 6) of maximum degree A (3 < A < 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.

Original languageEnglish
Title of host publicationGraph Algorithms and Applications 4
PublisherWorld Scientific Publishing
Pages33-78
Number of pages46
ISBN (Electronic)9789812773296
ISBN (Print)9812568441, 9789812568441
DOIs
Publication statusPublished - 1 Jan 2006
Externally publishedYes

Cite this

Wood, D. R. (2006). Lower bounds for the number of bends in three-dimensional orthogonal graph drawings. In Graph Algorithms and Applications 4 (pp. 33-78). World Scientific Publishing. https://doi.org/10.1142/9789812773296_0002