Ph.D. Thesis: Three-Dimensional Orthogonal Graph Drawing

School of Computer Science and Software Engineering, Monash University, 2000

Supervisor: Graham Farr


The master and student,
and the 2-bend K_7 The visualisation of relational information has many applications in diverse domains such as software engineering and cartography. Relational information is typically modelled by an abstract graph, where vertices are entities and edges represent relationships between entities. The aim of graph drawing is to automatically produce drawings of graphs which clearly reflect the inherent relational information.

Numerous graph drawing styles have been proposed in the literature. Orthogonal graph drawings have been widely studied due to their appropriateness in a variety of visualisation applications and in the design of VLSI circuitry. Most of the research conducted in graph drawing, including orthogonal drawings, has dealt with drawings in the plane. With the widespread availability of graphics workstations and the development of software systems for three-dimensional graphics, there has been recent interest in the design and analysis of algorithms for three-dimensional graph drawing.

This thesis is primarily concerned with problems related to the automatic generation of three-dimensional orthogonal graph drawings. Our methods also have application to two-dimensional orthogonal graph drawing and generalise to higher dimensional space.

In particular, we develop a number of models for three-dimensional orthogonal graph drawing, and within each model, algorithms are presented which explore trade-offs between the established aesthetic criteria. The main achievements include (1) an algorithm for producing three-dimensional orthogonal box-drawings with optimal volume for regular graphs, (2) an algorithm for producing degree-restricted three-dimensional orthogonal cube-drawings with optimal volume, (3) an algorithm which establishes the best known upper bound for the total number of bends in three-dimensional orthogonal point-drawings, and (4) an algorithm which establishes the best known upper bound for the volume of 3-D orthogonal point-drawings with three bends per edge route.

As a by-product of this investigation, we develop methods for a number of combinatorial problems of independent interest, including the balanced vertex ordering problem, equitable edge-colouring of multigraphs, and the maximum clique problem.

Download the thesis:
Single-sided A4 (286 pages)