The 26th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2000) was
held at Waldhaus Jakob in Konstanz Germany on 15{ 17 June 2000. It was organized by the
Algorithms and Data Structures Group of the Department of Computer and Information Science
University of K- stanz and sponsored by Deutsche Forschungsgemeinschaft (DFG) and Univ-
sit¨atsgesellschaft Konstanz. The workshop aims at uniting theory and practice by demonstrating
how graph-theoretic concepts can be applied to various areas in computer science or by
extracting new problems from applications. The goal is to present recent research results and
to identify and explore directions for future research. The workshop looks back on a remarkable
tradition of more than a quarter of a century. Previous Workshops have been organized in
various places in Europe and submissions come from all over the world. This year 57 attendees
from 13 di erent countries gathered in the relaxing atmosphere of Lake Constance also known as
the Bodensee. Out of 51 submis- ons the program committee carefully selected 26 papers for
presentation at the workshop. This selection re?ects current research directions among them
graph and network algorithms and their complexity algorithms for special graph cl- ses
communication networks and distributed algorithms. The present volume contains these papers
together with the survey presented in an invited lecture by Ingo Wegener (University of
Dortmund) and an extended abstract of the invited lecture given by Emo Welzl (ETH Zuric ¨ h).
