Graph-Theoretic Concepts in Computer Science: 32nd International Workshop, WG 2006, Bergen, Norway, June 22-23, 2006, Revised Papers

Front Matter....Pages -
Treewidth: Characterizations, Applications, and Computations....Pages 1-14
Locally Injective Graph Homomorphism: Lists Guarantee Dichotomy....Pages 15-26
Generalised Dualities and Finite Maximal Antichains....Pages 27-36
Chordal Deletion Is Fixed-Parameter Tractable....Pages 37-48
A Fixed-Parameter Algorithm for the Minimum Weight Triangulation Problem Based on Small Graph Separators....Pages 49-57
Divide-and-Color....Pages 58-67
Listing Chordal Graphs and Interval Graphs....Pages 68-77
A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set in Graphs....Pages 78-89
Improved Edge-Coloring with Three Colors....Pages 90-101
Vertex Coloring of Comparability+ k e and – k e Graphs....Pages 102-112
Convex Drawings of Graphs with Non-convex Boundary....Pages 113-124
How to Sell a Graph: Guidelines for Graph Retailers....Pages 125-136
Strip Graphs: Recognition and Scheduling....Pages 137-146
Approximating the Traffic Grooming Problem in Tree and Star Networks....Pages 147-158
Bounded Arboricity to Determine the Local Structure of Sparse Graphs....Pages 159-167
An Implicit Representation of Chordal Comparabilty Graphs in Linear-Time....Pages 168-178
Partitioned Probe Comparability Graphs....Pages 179-190
Computing Graph Polynomials on Graphs of Bounded Clique-Width....Pages 191-204
Generation of Graphs with Bounded Branchwidth....Pages 205-216
Minimal Proper Interval Completions....Pages 217-228
Monotony Properties of Connected Visible Graph Searching....Pages 229-240
Finding Intersection Models of Weakly Chordal Graphs....Pages 241-255
A Fully Dynamic Algorithm for the Recognition of P 4 -Sparse Graphs....Pages 256-268
Clique Graph Recognition Is NP-Complete....Pages 269-277
Homogeneity vs. Adjacency: Generalising Some Graph Decomposition Algorithms....Pages 278-288
Certifying Algorithms for Recognizing Proper Circular-Arc Graphs and Unit Circular-Arc Graphs....Pages 289-300
Graph Labelings Derived from Models in Distributed Computing....Pages 301-312
Flexible Matchings....Pages 313-324
Simultaneous Graph Embeddings with Fixed Edges....Pages 325-335
Approximation Algorithms for Restricted Cycle Covers Based on Cycle Decompositions....Pages 336-347
Circular-Perfect Concave-Round Graphs....Pages 348-355
Back Matter....Pages -