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

Research output: Contribution to journalArticleResearchpeer-review

29 Citations (Scopus)

Abstract

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 five; this is the only known non-trivial class of graphs admitting two-bend drawings.
Original languageEnglish
Pages (from-to)151-178
Number of pages28
JournalTheoretical Computer Science
Volume299
Issue number1-3
DOIs
Publication statusPublished - 2003
Externally publishedYes

Cite this