Algorithms Seminar Winter 2001

In Computer Science we often use a graph to model relational information in programs, data structures and databases, for example. Graph drawing is concerned with the automatic drawing of an abstract graph with the aim of highlighting the inherent relational information. In recent years there has been a rapid growth in the development of methods for graph drawing. A commonly used graph drawing convention is to route each edge as a polyline composed of axis-parallel straight line segments, a so called `orthogonal graph drawing'. Orthogonal drawings with few bends are considered aesthetically pleasing and also have important applications in the automatic layout of VLSI circuits. While most research in orthogonal graph drawing has centred on the two-dimensional case, recently algorithms for three-dimensional orthogonal graph drawing have also been developed. The question of whether every graph has a three-dimensional orthogonal drawing with at most two bends per edge, called the `two-bends problem', is important for visualisation purposes and of theoretical interest. In this seminar we describe a number of approaches that have been taken in an attempt to solve the two-bends problem; in particular, we present the best known upper and lower bounds on the number of bends in three-dimensional orthogonal graph drawings.