Abstract 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. |