No Title

GRAPH DRAWING

One in a series of snapshots of applications of research in discrete mathematics.

PETER EADES
UNIVERSITY OF NEWCASTLE
AUSTRALIA

The Context

Since the mid 1980s, graphics workstations have become standard tools for software and information engineers. An important consequence has been that relational information, once handled textually, is now commonly displayed and manipulated graphically. Relational visualisation has become an essential tool for programmers and analysts. Thus modern CASE tools, file systems, network configuration tools, and syntax-driven editors usually include a module for visualising their data. A bibliographic survey of current research in this area is in [1].

The basic visualisation pipeline is illustrated below. The application may be a program, a database, a data structure, a communication or security protocol, or a similar computational structure.

The steps of the pipeline are:

Modelling: Critical information in such applications is relational: it consists of a set of entities and relations between the entities. Mathematically, this relational information is usually modelled as a graph: the entities are nodes, and the relations are edges. At this stage, the graph is purely combinatorial and has no geometric attributes. The process of extracting the relations from the application is the modelling step.
Layout: The graphs created by the modelling step are conventionally drawn with nodes represented by boxes (perhaps enclosing some text) and edges represented by lines between the boxes. The process of adding geometric attributes to the graph is the layout step.

The Problem

The most difficult problem in constructing a specific visualization pipeline for a specific application is to assign a position for each node and assign a curve for each edge. The resulting picture should illuminate the application, that is, it should help the user to understand and remember the object being visualised. A good layout can be a picture worth a thousand words; a poor layout can confuse or mislead.

The layout must satisfy several aesthetics, that is, formal requirements for a ``good'' layout. Aesthetics differ from one application to another, but typically include items such as the avoidance of edge crossings, maximisation of symmetry, and the preservation of a minimum distance between nodes. Further, in many applications it is important to tie aesthetics of the visual image to the quality of the application object under consideration; that is, image beauty must be tied to application quality.

Algorithms for producing a layout with the desired aesthetics must be designed, analysed, implemented and tested.

The Role of Discrete Mathematics

Long before the use of graphical workstations, Discrete Mathematicians studied problems of graph layout. This research had been invaluable for modern graph layout strategies. For example, the papers of Farey early this century, of Steinitz in the 1930s, and of Tutte in the 1960s are commonly quoted in papers describing layout of graphs for visualization.

Many modern graph drawing techniques use theorems about flows in networks, for example the well known max-flow-min-cut theorem.

The Benefits of Further Research

The graph layout problem is still largely unsolved; that is, we still do not know a simple algorithm which can achieve the requirements of relational visualization. Grand challenge problems, such as visualizing the internet, will only be tractable with a deeper knowledge of graph theory.

For More Information

Since 1992 there have been annual conferences in Graph Drawing, attended by a range of researchers from discrete mathematicians to software engineers. Contact Peter Eades eades@cs.newcastle.edu.au.