Towards a 2-bends algorithm for three-dimensional orthogonal graph drawing
David R. Wood · 1997
Two recent algorithms for 3-dimensional orthogonal graph drawing both guarantee no more than 3 bends per edge, yet no graph has been shown to necessarily require a 3-bend edge. In this paper we present progress towards an algorithm which will produce an orthogonal graph drawing of an arbitrary graph with no more than 2 bends per edge. 1 Introduction While the investigation of graph drawing in the plane has been extensive (see [5] for a bibliographic survey), there has been recent interest in graph visualisation in three dimensions. Applications include VLSI circuit design[12, 14] and software engineering[10, 13]. The 3-dimensional orthogonal grid which consists of grid points in 3-space with integer coordinates, together with the axis-parallel grid lines determined by these points. An orthogonal grid drawing of a graph G places the vertices of G at grid points and routes the edges of G along sequences of contiguous segments contained in grid lines. Edge routes are allowed to contain...