This book constitutes the thoroughly refereed post-proceedings of the 31st International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2005, held in Metz, France in June 2005.

The 38 revised full papers presented together with 2 invited papers were carefully selected from 125 submissions. The papers provide a wealth of new results for various classes of graphs, graph computations, graph algorithms, and graph-theoretical applications in various fields. 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 of future research.