Treewidth: Characterizations, Applications, and Computations -- Locally Injective Graph Homomorphism: Lists Guarantee Dichotomy -- Generalised Dualities and Finite Maximal Antichains -- Chordal Deletion Is Fixed-Parameter Tractable -- A Fixed-Parameter Algorithm for the Minimum Weight Triangulation Problem Based on Small Graph Separators -- Divide-and-Color -- Listing Chordal Graphs and Interval Graphs -- A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set in Graphs -- Improved Edge-Coloring with Three Colors -- Vertex Coloring of Comparability+ke and –ke Graphs -- Convex Drawings of Graphs with Non-convex Boundary -- How to Sell a Graph: Guidelines for Graph Retailers -- Strip Graphs: Recognition and Scheduling -- Approximating the Traffic Grooming Problem in Tree and Star Networks -- Bounded Arboricity to Determine the Local Structure of Sparse Graphs -- An Implicit Representation of Chordal Comparabilty Graphs in Linear-Time -- Partitioned Probe Comparability Graphs -- Computing Graph Polynomials on Graphs of Bounded Clique-Width -- Generation of Graphs with Bounded Branchwidth -- Minimal Proper Interval Completions -- Monotony Properties of Connected Visible Graph Searching -- Finding Intersection Models of Weakly Chordal Graphs -- A Fully Dynamic Algorithm for the Recognition of P 4-Sparse Graphs -- Clique Graph Recognition Is NP-Complete -- Homogeneity vs. Adjacency: Generalising Some Graph Decomposition Algorithms -- Certifying Algorithms for Recognizing Proper Circular-Arc Graphs and Unit Circular-Arc Graphs -- Graph Labelings Derived from Models in Distributed Computing -- Flexible Matchings -- Simultaneous Graph Embeddings with Fixed Edges -- Approximation Algorithms for Restricted Cycle Covers Based on Cycle Decompositions -- Circular-Perfect Concave-Round Graphs.

This book constitutes the thoroughly refereed post-proceedings of the 32nd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2006, held in Bergen, Norway in June 2006. The 30 revised full papers presented together with 1 invited paper were carefully selected from 91 submissions. The papers address all aspects of graph-theoretic concepts in computer science such as structural graph theory, sequential, parallel, and distributed graph and network algorithms and their complexity, graph grammars and graph rewriting systems, graph-based modeling, graph-drawing and layout, diagram methods, and graph-theoretical applications in various fields.