List of accepted papers

The following 28 papers have been selected by the PC for presentation at WG 2009:

• George Mertzios, Ignasi Sau and Shmuel Zaks.
  A New Intersection Model and Improved Algorithms for Tolerance Graphs
• Lucia Draque Penso, Dieter Rautenbach and Jayme Luiz Szwarcfiter.
  Cycles, Paths, Connectivity and Diameter in Distance Graphs
• Zhentao Li and Ignasi Sau.
  Graph Partitioning and Traffic Grooming with Bounded Degree Request Graph
• Frank Kammer and Torsten Tholey.
  The k-Disjoint Path Problem on Chordal Graphs
• Shiri Chechik and David Peleg.
  Low-Port Tree Representations
• Torben Hagerup.
  An even simpler linear-time algorithm for verifying minimum spanning trees
• Michael Fellows, Jiong Guo and Iyad Kanj.
  The Parameterized Complexity of Some Minimum Label Problems
• Iyad Kanj, Andreas Wiese and Fenghui Zhang.
  Local Algorithms for Edge Colorings in UDGs
• Shimon Shrem, Michal Stern and Martin Golumbic.
  Smallest Odd Holes in Claw-Free Graphs
• Stéphane Grumbach and Zhilin Wu.
  Logical locality entails frugal distributed computation over graphs (extended abstract)
• Bastian Katz, Ignaz Rutter and Gerhard Woeginger.
  An algorithmic study of switch graphs
• Daniel Meister and Jan Arne Telle.
  Chordal digraphs
• Yoshio Okamoto, Ryuhei Uehara and Takeaki Uno.
  Counting the Number of Matchings in Chordal and Chordal Bipartite Graph Classes
• Gary MacGillivray, André Raspaud and Jacobus Swarts.
  Injective Oriented Colourings
• Rajiv Gandhi, Bradford Greening, Jr, Sriram Pemmaraju and Rajiv Raman.
  Sub-coloring and Hypocoloring Interval Graphs
• Petr Golovach, Jan Kratochvil and Ondrej Suchy.
  Parameterized Complexity of Generalized Domination Problems
• Mamadou Moustapha Kanté and Michaël Rao.
  Directed Rank-Width and Displit Decomposition
• Ilia Averbouch, Johann Makowsky and Peter Tittmann.
  A Graph Polynomial Arising from Community Structure
• Gruia Calinescu, Cristina Fernandes and Hemanshu Kaul.
  Maximum Series-Parallel Subgraph
• Hajo Broersma, Fedor Fomin, Pim van 't Hof and Daniel Paulusma.
  Fast exact algorithms for hamiltonicity in claw-free graphs
• Pim van 't Hof, Marcin Kaminski and Daniel Paulusma.
  Finding induced paths of given parity in claw-free graphs
• Sebastian Ordyniak and Stephan Kreutzer.
  Distance d-Domination Games
• Frank Gurski and Egon Wanke.
  On module-composed graphs
• Christophe Crespelle.
  Fully Dynamic Representations of Interval Graphs
• Fedor Fomin, Daniel Lokshtanov and Saket Saurabh.
  An Exact Algorithm for Minimum Distortion Embedding
• René Sitters and Alexander Grigoriev.
  Connected feedback vertex set in planar graphs
• Van Bang Le and Ngoc Tuy Nguyen.
  Hardness Results and Efficient Algorithms for Graph Powers
• Henning Fernau, Serge Gaspers and Daniel Raible.
  Exact and Parameterized Algorithms for Max Internal Spanning Tree