27. – 31. Juli 1998, Dagstuhl-Seminar 98301

Graph Algorithms and Applications


T. Nishizeki (Tohoku Univ. Sendai), R. Tamassia (Brown), D. Wagner (Konstanz)

Auskunft zu diesem Dagstuhl-Seminar erteilt

Dagstuhl Service Team


Dagstuhl's Impact: Dokumente verfügbar
Dagstuhl-Seminar-Report 219



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.


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.


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.

Related Dagstuhl-Seminar


In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.


Download Übersichtsflyer (PDF).

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.


Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.