Graph-Theoretic Concepts in Computer Science: 29th International Workshop, WG 2003. Elspeet, The Netherlands, June 19-21, 2003. Revised Papers

Michael R. Fellows (auth.), Hans L. Bodlaender (eds.)3540204520, 9783540204527

The 29th International Workshop on Graph-Theoretic Concepts in Computer Science(WG2003)washeldintheMennorodeconferenceCenterinElspeet,The Netherlands.TheworkshopwasorganizedbytheCenterforAlgorithmicSystems of the Institute of Information and Computing Sciences of Utrecht University. The workshop took place June 19–21, 2003. The 72 participants of WG 2003 came from universities and research institutes from 18 di?erent countries and ?ve di?erent continents. The workshop looks back at a long tradition. It was ?rst held in 1975, and has been held 20 times in Germany, twice in Austria, and once in Italy, Slo- kia, Switzerland, and the Czech Republic, and has now been held for the third time in The Netherlands. The workshop aims at uniting theory and practice by demonstrating how graph-theoretic concepts can be applied to various areas in computerscience,orbyextractingnewproblemsfromapplications.Itisdevoted to the theoretical and practical aspects of graph concepts in computer science. The goal is to present recent research results and to identify and explore – rections of future research. The talks given at the workshop showed how recent research results from algorithmic graph theory can be used in computer science and which graph-theoretic questions arise from new developments in computer science.

---

Table of contents :
Front Matter….Pages –
Blow-Ups, Win/Win’s, and Crown Rules: Some New Directions in FPT ….Pages 1-12
Matching, Edge-Colouring, and Dimers….Pages 13-22
Minimum Flow Time Graph Ordering….Pages 23-33
Searching Is Not Jumping….Pages 34-45
Incremental Integration Tools for Chemical Engineering: An Industrial Application of Triple Graph Grammars….Pages 46-57
The Minimum Degree Heuristic and the Minimal Triangulation Process….Pages 58-70
Generalized Parametric Multi-terminal Flows Problem….Pages 71-80
Canonical Decomposition of Outerplanar Maps and Application to Enumeration, Coding, and Generation….Pages 81-92
The Complexity of the Matching-Cut Problem for Planar Graphs and Other Graph Classes….Pages 93-105
Tree Spanners for Bipartite Graphs and Probe Interval Graphs….Pages 106-118
A Simple Linear Time LexBFS Cograph Recognition Algorithm….Pages 119-130
Backbone Colorings for Networks….Pages 131-142
Greedy Edge-Disjoint Paths in Complete Graphs….Pages 143-155
Graph-Based Approaches to Software Watermarking….Pages 156-167
Completely Connected Clustered Graphs….Pages 168-179
An FPT Algorithm for Set Splitting….Pages 180-191
Drawing Planar Graphs on a Curve….Pages 192-204
Tree-Partitions of k -Trees with Applications in Graph Layout….Pages 205-217
Resource Allocation Problems in Multifiber WDM Tree Networks….Pages 218-229
An Improved Upper Bound on the Crossing Number of the Hypercube….Pages 230-236
NCE Graph Grammars and Clique-Width….Pages 237-248
Chordal Probe Graphs….Pages 249-260
Subgraph Induced Planar Connectivity Augmentation….Pages 261-272
On the Recognition of General Partition Graphs….Pages 273-283
Short Cycles in Planar Graphs….Pages 284-296
Complexity of Hypergraph Coloring and Seidel’s Switching….Pages 297-308
Feedback Vertex Set and Longest Induced Path on AT-Free Graphs….Pages 309-321
The Complexity of Graph Contractions….Pages 322-333
Tree Spanners, Cayley Graphs, and Diametrically Uniform Graphs….Pages 334-345
The Probabilistic Minimum Coloring Problem….Pages 346-357
Recognizing Bipolarizable and P 4 -Simplicial Graphs….Pages 358-369
Coloring Powers of Graphs of Bounded Clique-Width….Pages 370-382
Erratum: Cycles in Generalized Networks….Pages 383-383
Back Matter….Pages –