Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00060
Lower Bounds for the Number of Bends in Three-Dimensional
Orthogonal Graph Drawings
Vol. 7, no. 1, pp. 33-77, 2003. Regular paper.
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 ∆
(3 ≤ ∆ ≤ 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.
|
Journal Supporters
|