July 27 – 31 , 1998, Dagstuhl Seminar 98301

Graph Algorithms and Applications


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

For support, please contact

Dagstuhl Service Team


Dagstuhl's Impact: Documents available
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 the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.


Download overview leaflet (PDF).

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.


Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.