Optimal three-dimensional orthogonal graph drawing in the general position model

✍ Scribed by David R. Wood

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 636 KB
• Volume: 299
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(02)00044-0

✦ Synopsis

Let G be a graph with maximum degree at most six. A three-dimensional orthogonal drawing of G positions the vertices at grid-points in the three-dimensional orthogonal grid, and routes edges along grid lines such that edge routes only intersect at common end-vertices. In this paper, we consider three-dimensional orthogonal drawings in the general position model; here no two vertices are in a common grid-plane. Minimising the number of bends in an orthogonal drawing is an important aesthetic criterion, and is NP-hard for general position drawings. We present an algorithm for producing general position drawings with an average of at most 2 2 7 bends per edge. This result is the best known upper bound on the number of bends in three-dimensional orthogonal drawings, and is optimal for general position drawings of K7. The same algorithm produces drawings with two bends per edge for graphs with maximum degree at most ÿve; this is the only known non-trivial class of graphs admitting two-bend drawings.