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

Treewidth : Characterizations, Applications, And Computations / Hans L. Bodlaender -- Locally Injective Graph Homomorphism : Lists Guarantee Dichotomy / Jiri Fiala And Jan Kratochvil -- Generalised Dualities And Finite Maximal Antichains / Jan Foniok, Jaroslav Nesetril And Claude Tardif -- Chordal Deletion Is Fixed-parameter Tractable / Daniel Marx -- A Fixed-parameter Algorithm For The Minimum Weight Triangulation Problem Based On Small Graph Separators / Christian Knauer And Andreas Spillner -- Divide-and-color / Joachim Kneis, Daniel Molle, Stefan Richter And Peter Rossmanith -- Listing Chordal Graphs And Interval Graphs / Masashi Kiyomi, Shuji Kijima And Takeaki Uno -- A Branch-and-reduce Algorithm For Finding A Minimum Independent Dominating Set In Graphs / Serge Gaspers And Mathieu Liedloff -- Improved Edge-coloring With Three Colors / Lukasz Kowalik -- Vertex Coloring Of Comparability+ke And -ke Graphs / Yasuhiko Takenaga And Kenichi Higashide -- Convex Drawings Of Graphs With Non-convex Boundary / Seok-hee Hong And Hiroshi Nagamochi -- How To Sell A Graph : Guidelines For Graph Retailers / Alexander Grigoriev, Joyce Van Loon, Rene Sitters And Marc Uetz -- Strip Graphs : Recognition And Scheduling / Magnus M. Halldorsson And Ragnar K. Karlsson -- Approximating The Traffic Grooming Problem In Tree And Star Networks / Michele Flammini, Gianpiero Monaco, Luca Mascardelli, Mordechai Shalom And Shmuel Zaks -- Bounded Arboricity To Determine The Local Structure Of Sparse Graphs / Gaurav Goel And Jens Gustedt -- An Implicit Representation Of Chordal Comparabilty Graphs In Linear-time / Andrew R. Curtis, Clemente Izurieta, Benson Joeris, Scott Lundberg And Ross M. Mcconnell -- Partitioned Probe Comparability Graphs / David B. Chandler, Maw-shang Chang, Ton Kloks, Jiping Liu And Sheng-lung Peng -- Computing Graph Polynomials On Graphs Of Bounded Clique-width / J.a. Makowsky, Udi Rotics, Ilya Averbouch And Benny Godlin -- Generation Of Graphs With Bounded Branchwidth / Christophe Paul, Andrzej Proskurowski And Jan Arne Telle -- Minimal Proper Interval Completions / Ivan Rapaport, Karol Suchan And Ioan Todinca -- Monotony Properties Of Connected Visible Graph Searching / Pierre Fraigniaud And Nicolas Nisse -- Finding Intersection Models Of Weakly Chordal Graphs / Martin Charles Golumbic, Marina Lipshteyn And Michal Stern -- A Fully Dynamic Algorithm For The Recognition Of P[subscript 4]-sparse Graphs / Stavros D. Nikolopoulos, Leonidas Palios And Charis Papadopoulos -- Clique Graph Recognition Is Np-complete / L. Alcon, L. Faria, C.m.h. De Figueiredo And M. Gutierrez -- Homogeneity Vs. Adjacency : Generalising Some Graph Decomposition Algorithms / B.-m. Bui Xuan, M. Habib, V. Limouzy And F. De Montgolfier -- Certifying Algorithms For Recognizing Proper Circular-arc Graphs And Unit Circular-arc Graphs / Haim Kaplan And Yahav Nussbaum -- Graph Labelings Derived From Models In Distributed Computing / Jeremie Chalopin And Daniel Paulusma -- Flexible Matchings / Miklos Bartha And Miklos Kresz -- Simultaneous Graph Embeddings With Fixed Edges / Elisabeth Gassner, Michael Junger, Merijam Percan, Marcus Schaefer And Michael Schulz -- Approximation Algorithms For Restricted Cycle Covers Based On Cycle Decompositions / Bodo Manthey -- Circular-perfect Concave-round Graphs / Sylvain Coulonges. Fedor V. Fomin (ed.). Includes Bibliographical References And Index. The 32nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2006) was held on the island of Sotra close to the city of Bergen on the west coast of Norway. The workshop was organized by the Algorithms Research Group at the Department of Informatics, University of Bergen, and it took place from June 22 to June 24. The 78 participants of WG 2006 came from the universities and research institutes of 17 di?erent countries. The WG 2006 workshop continues the series of 31 previous WG workshops. Since 1975,WG has taken place 20 times in Germany, four times in The Neth- lands, twice in Austria as well as oncein France, in Italy, in Slovakia, in Switz- land and in the Czech Republic, and has now been held for the?rst time in Norway. The workshop aims at uniting theory and practice by demonstrating how graph-theoretic concepts can be applied to various areas in computer s- ence, or by extracting new problems from applications. The goal is to present recent research results and to identify and explore directions of future research. The talks showed how recent researchresults from algorithmic graph theory can be used in computer science and which graph-theoreticquestions arisefrom new developments in computer science. There were two fascinating invited lectures by Hans Bodlaender (Utrecht, The Netherlands) and Tandy Warnow (Austin, USA) 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. [From publisher's description]