Background

Algorithmic graph theory is a classical area of research by now and has been rapidly expanding during the last three decades. In many different contexts of computer science and applications modelling problems by graphs is a natural and canonical process. Graph--theoretic concepts and algorithms play an important role in many fields of application, e.g. in communication network design, VLSI-design, CAD, traffic optimisation or network visualisation.

Beside the design and analysis of algorithms to solve fundamental graph problems, the application of those methods to real world problems is an interesting task for researchers in algorithmic graph theory. Recently, researchers also started developing software systems for graph algorithms to provide effective computational tools to support applications prototyping, algorithm animation or further algorithmic research. Several algorithm libraries, algorithm animation tools or special purpose software packages, e.g. graph editors and graph drawing software, have been developed within the last five to ten years.

Goals

This seminar was intended to bring together researchers from different areas in algorithmic graph theory and from application. One aim was to support the collaboration between computer scientists, mathematicians, and applied researchers, both from academia and industry in the field. It was a follow-up of a seminar on the same topic held in 1996.

Main topics of interest were on one hand classical problems from graph theory as connectivity and cuts, paths and flows, colouring problems and theoretical aspects of graph drawing. On the other hand, problems from application where those concepts are of special importance were discussed. Particular emphasis was placed on experimental research and aspects of the implementation of graph algorithms. One of the central topics was " graph drawing " which addresses the problem of visualising structural information. The automatic generation of drawings of graphs has important applications in key computer science technologies such as database design, software engineering, VLSI and network design and visual interfaces. Applications in other sciences concern all fields of visual data mining e.g. in engineering, chemistry and biology, archaeology or sociology and political science. The interaction between theoretical advances and implemented solutions is an important part of the area of graph drawing.

Results

We had 48 participants from Austria, Germany, France, Italy, Poland, Hungary, Slovenia, Israel, Australia, USA, Canada, Japan and Korea. During the workshop 38 lectures, some including also software demonstrations have been given. Most of the talks presented very recent research results. The informal character of the workshop made it possible to have intensive discussions. There was an open-problem-session and a lively discussion on new directions in graph drawing. Both, senior researchers as well as young researchers contributed to this seminar.

All participants were greatly pleased that several young researchers were able to attend this workshop due to special European funding from the TMR-Program that the Dagstuhl Institution was able to organise. This contributed to the especially inspiring and refreshing atmosphere of the seminar. Moreover, Schloss Dagstuhl and its staff provided a very convenient and stimulating environment.

The organisers plan to edit a special volume of the "Journal of Graph Algorithms and Applications" with selected papers addressing areas covered by the seminar.