May 13 – 17 , 1996, Dagstuhl Seminar 9620

Graph Algorithms and Applications


T. Nishizeki, R. Tamassia, D. Wagner

For support, please contact

Dagstuhl Service Team


Dagstuhl's Impact: Documents available
Dagstuhl-Seminar-Report 145


In many fields of applications graphs or networks play an important role for understanding a concrete situation and modelling problems. The development of algorithms for communication problems, traffic optimization, scheduling or VLSI-design is for example based on graphs. Algorithmic graph theory is a classical area of research by now and has been rapidly expanding during the last three decades. Especially, the interplay between theory and application gave research in this area again and again new impetus.

While the complexity of today’s “real world” problems is increasing the design of “sophisticated” algorithms is an ambitious task. Numerous newly invented problems coming from new fields of applications have attracted the attention of researchers in algorithmic graph theory. But, in recent years also classical problems were studied again. For several fundamental graph problems efficient and simple algorithms were designed in view of the computer implementation of such algorithms.

This seminar was intended to bring together researchers from different areas in algorithmic graph theory. Particular emphasis was placed on applications, experimental research and aspects of the implementation of graph algorithms. The participants had the opportunity to exchange ideas and discuss new trends in algorithmic graph theory. Main topics of interest were efficient graph algorithms, graph drawing, algorithm animation with graphs, implementation of graph algorithms and applications in VLSI-design, traffic optimization, and CAD.

We had 36 participants from different European countries, Australia, USA, Canada, Japan and Taiwan. During the workshop 28 lectures have been presented and two software demonstrations. There was also an open-problem-session on Tuesday evening and a lively discussion on problems from different fields of application. Schloß Dagstuhl and its staff provided a very convenient and stimulating environment. All participants appreciated the cordial atmosphere. The organizers wish to thank all those who helped make the workshop a fruitful research experience.

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.