Graph drawing deals with the problem of communicating the structure of relational data through diagrams, or drawings. The field builds on early research in flowchart design, CASE tools, visual programming interfaces, VLSI design, database systems, and software engineering. 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.

The ability to represent relational information in a geometric 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. Graph drawing tools are needed in a growing number of scientific disciplines, including bioinformatics, physics, and sociology. Within the computing disciplines, graph drawing techniques are essential in areas such as networking, internet traffic control, and bioinformatics. For example, Internet Service Providers and web caching providers must be able to quickly identify patterns and trends in internet traffic. Visualization of network topology is used to identify and analyze characteristic patterns leading to better functionality.

One of the main current challenges in graph drawing research is to deal effectively with very large graphs, and graphs that evolve through time.

Recent technological advances have brought about increased data volumes and increased data complexity. However, visualization of large and complex graphs is difficult, given the constraints imposed by the current technology (limited number of pixels on a screen) and the complexity of the graphs to be displayed (millions of nodes and edges). In many fields, such as telecommunication, databases, and software engineering, the models contain millions of objects and relationships. Models without natural geometric placement often require hours to compute even an initial layout. Reasons are the complex nature of the algorithms and the fact that existing algorithms do not scale well.

In order to deal with huge graphs, we need to develop alternative models and algorithms. Possible techniques include the identification and collapsing of subgraphs, focus and context, and interactive browsing techniques. In addition, the development of new clustering techniques including the identification and representation of clusters (groups of vertices belonging together) plays an important role.

In many applications the models are dynamic, evolving over time, e.g., telephone graphs in which telephones are the objects and calls are the relationships. Even the fastest graphics systems using state of the art drawing and rendering algorithms fail to provide interactive visualization for such complex models.

Since graph drawing is mainly application driven, we focused our research during the seminar on the visualization of large and dynamic graphs in the following application domains: bioinformatics (visualizing biochemical networks such as protein interaction networks, regulatory and signaling pathways), software engineering (e.g., UML class diagrams, memory graphs), internet and telecommunications visualization, and social network analysis.

Good attendance and excellent presentations contributed to the general success of the seminar. The aims and achievements of the seminar are summarized below.

Aims

In the application, we formulated the following aims for the Dagstuhl seminar:

1. To address the long-standing open problems related to the visualization and interaction with large and dynamic networks;
2. To bring together theoreticians and practitioners from the targeted graph drawing application areas: bioinformatics, software engineering, internet and telecommunication visualization, and social network analysis;

The main research topics represent significant long-standing open problems in the area of graph drawing for which no satisfactory solutions are yet known. In order to make progress and obtain new results, it is necessary that theoreticians work together with practitioners and applied researchers as well as with researchers from closely related areas, such as information visualization and software visualization. Moreover, close cooperation with users in the considered application domains is essential for the successful development of effective tools for the visualization and interaction with large and dynamic networks.

Therefore, we invited researchers from the areas of pure graph theory, graph algorithms, and information visualization, as well as from the targeted application areas: computational biology, software engineering, internet and telecommunication visualization, and social network analysis. Our objective was to provide the opportunity to get these groups together in order to work on the emergent problems.

Achievements

Over forty participants from both academia and industry attended the seminar. Over one third of the attendees were graduate and postdoctoral students. There were representatives from more than ten countries, including Germany, Austria, United Kingdom, Ireland, Italy, Slovenia, Turkey, Canada, Australia, and USA. The achievements of the seminar can be summarized as follows:

1. We were lucky to enjoy a number of stimulating presentations on the core topics of the seminar. In particular, the presentations covered new approaches to the layout of large graphs, new ideas about evolving and dynamic graphs, as well as new visualization paradigms.
2. We enjoyed two survey lectures on the graph drawing aspects of bioinformatics and another two lectures on the visualization of social networks. In addition, we learned about novel applications of graph drawing techniques to problems in nano-technology and rank aggregation.
3. The graph drawing e-print archive, gdea was unveiled during the seminar. It provides a powerful depository and search interface for graph-drawing related publications. Staff members for gdea were also appointed during the seminar.
4. Solutions to some open problems were found during the seminar and close interactions led to new collaborations.

Beyond the survey lectures, highlights of the seminar included a lecture on the psychology of visual perception through empirical studies, and lectures on applications of graph drawing in non-traditional areas such as nano-technology. An open problem session led to successful problem solving. The report of the open problem session is included with the seminar materials. New cooperations, e.g., between Irish and German researchers, led to a joint article that is currently in preparation.

In summary, it is our impression that the participants enjoyed the great scientific atmosphere offered by Schloß Dagstuhl, and profited from the scientific program. Several attendees commented on the week of the seminar being one of the most enjoyable research experience they have had. We are grateful for having had the opportunity to organize this seminar.

Special thanks are due to Christoph Buchheim and Carsten Gutwenger for their assistance in running the seminar smoothly and taking care of the documentation.