TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 98301

Graph Algorithms and Applications

( Jul 27 – Jul 31, 1998 )

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/98301

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




Results

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.


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

Related Seminars
  • Dagstuhl Seminar 9620: Graph Algorithms and Applications (1996-05-13 - 1996-05-17) (Details)