Graph drawing deals with the problem of communicating the structure of relational data through diagrams, or drawings. Graphs with vertices and edges are typically used to model relational data. The vertices represent the objects (or data points) and the edges represent the relationships between the objects. The main problem in relational visualization is to display the data in a meaningful fashion that may heavily depend on the application domain. Some of the application areas where graph drawing tools are needed include computer science (data base design, data mining, software engineering), bioinformatics (metabolic networks, protein-protein interaction), business informatics (business process models), and the social sciences and criminalistics (social networks, phone-call graphs).

The ability to represent relational information in a graphical form is a powerful tool which allows us to perform analysis through visual exploration. With the aid of graph visualization we can find important patterns, trends, and correlations. Real-world applications such as bioinformatics and sociology pose additional challenges, e.g., semantic information carried by the diagram has to be used for obtaining meaningful layouts and application-specific drawing conventions need to be fulfilled. Moreover, the underlying data often stems from huge data bases, but only a small fraction shall be displayed at a time; the user interactively selects the data to be displayed and explores the graph by expanding interesting and collapsing irrelevant parts. This requires powerful graph exploration tools with navigation capabilities that allow dynamic adaption of the graph layout in real time.

In this seminar we focused on the application of graph drawing in two important application domains: bioinformatics (metabolic pathways, regulatory networks, protein-protein interaction)and social sciences and criminalistics (case information diagrams, phone-call graphs). In both application domains, the underlying information is usually stored in large data bases constituting a huge and complex graph, but only a suitable fraction of this graph is visualized; the selection of that subgraph is guided by the user and even more user interaction occurs in order to further explore the underlying graph. Thus, the user becomes a central actor that triggers dynamic updates of the displayed graph and its layout. The support of application-specific update functionality in conjunction with high quality graph layout is essential for achieving user acceptance in the targeted application areas.

The interactive navigation through the graph poses new challenges to graph drawing algorithms. Whereas traditional graph drawing deals with the visualization of static graphs, we are now concerned with graphs that change over time, and the layout has to be adjusted in real time. The new layout has to observe aesthetic and application specific drawing criteria, as well as the preservation of the user's mental map; in particular only few changes in the layout are desired.

A similar dynamic component occurs in the visualization of graphs that evolve over time like minute-by-minute phone-call graphs which have application in police investigations. Here, we have a graph at each time point and an edge corresponds to a phone call between two telephones. In contrast to interactive navigation, we know in advance all of the changes the graph will undergo, and we can exploit this fact for producing a smoother animation sequence.

In summary, it is our impression that the participants enjoyed the great scientific atmosphere offered by Schloss Dagstuhl, and profited from the scientific program. We are grateful for having had the opportunity to organize this seminar. Special thanks are due to Carsten Gutwenger and Karsten Klein for their assistance in the organization and the running of the seminar.