Graph Drawing

A diagram is composed of a collection of entities with specified pairwise relations. The underlying abstract structure is called graph in mathematics and computer science. A diagram layout is a graphical representation of a diagram whose purpose is to make the visual perception of its contents easy. The young scientific discipline automatic graph drawing is concerned with design, analysis, implementation and experimental evaluation of algorithms for the automatic layout of diagrams on computers.

There are various scientific and commercial applications of automatic graph drawing:

• software (re-)engineering (class diagrams, data flow diagrams, ...)
• bioinformatics (pathways, interaction networks, ...)
• networks (computer networks, social networks, ...)
• technical processes (finite automata, ...)
• data bases (data models, entity relationship diagrams, ...)
• business process modelling (organization diagrams, event driven process chains, ...)

The complexity of the task is often underestimated. Many commercial software systems produce results of minor quality.

We develop mathematical methods and efficient algorithms for automatic graph drawing. The most relevant disciplines are combinatorial optimization (crossing minimization, bend minimization, compaction) and topology (planar graphs, planar embeddings), our research includes the development of efficient algorithms (planarity testing, planar embedding, network flows, linear programming) and the application of modern software engineering concepts.

Links

Graph Drawing in Vienna

Currently, our Graph-Drawing pages still reside at the Technical University in beautiful Vienna.

PG 478. OGDF: An Open Graph Drawing Framework

Information on our Student-Project (aka. PG) on Graph Drawing (German only)