Tech Report CS-96-13

Where to Draw the Line

Ashim Garg

April 1996

Abstract:

Graph Drawing (also known as Graph Visualization) tackles the problem of representing graphs on a visual medium such as computer screen, printer etc. Many applications such as software engineering, data base design, project planning, VLSI design, multimedia etc., have data structures that can be represented as graphs. With the ever increasing complexity of these and new applications, and availability of hardware supporting visualization, the area of graph drawing is increasingly getting more attention from both practitioners and researchers.

In a typical drawing of a graph, the vertices are represented as symbols such as circles, dots or boxes, etc., and the edges are drawn as continuous curves joining their end points. Often, the edges are simply drawn as (straight- or poly-) lines joining their end points (and hence the title of this thesis), followed by an optional transformation into smooth curves. The goal of research in graph drawing is to develop techniques for constructing good drawings of the input graphs. Informally speaking, a drawing is considered ``good'' if it is able to communicate effectively and clearly, the information being displayed in the drawing. Several desirable properties of a good drawing, that have been identified are: small area, minimum edge crossings, large angles between edges, symmetry, small number of edge-bends, upwardness, clustering or aligning of related vertices etc. In this thesis, we have addressed the problem of constructing drawings that exhibit some of these properties, and have presented several new techniques that provide answers to these problems. The problems we have considered relate to the following drawings:

- Planar upward drawings of directed acyclic graphs, i.e., planar drawings in which edges flow in the same direction (usually along $y$-axis). - Planar straight-line drawings of planar graphs, in which the angles between edges incident on the same vertex have large magnitudes. - Drawings of angle graphs, i.e., graphs with angles specified between edges incident on the same vertex. - Planar orthogonal drawings (edges drawn as a chain of horizontal and vertical line-segments) of degree-four graphs, with minimum number of edge-bends.

(complete text in pdf or gzipped postscript)