Graph-Theoretic Concepts in Computer Science

1. Front Matter

   PDF

2. Graph-Theoretic Solutions to Computational Geometry Problems

   • David Eppstein

   Pages 1-16

3. Algorithms for Classes of Graphs with Bounded Expansion

   • Zdeněk Dvořák, Daniel Král’

   Pages 17-32

4. A Graph Polynomial Arising from Community Structure (Extended Abstract)

   • Ilia Averbouch, Johann A. Makowsky, Peter Tittmann

   Pages 33-43

5. Fast Exact Algorithms for Hamiltonicity in Claw-Free Graphs

   • Hajo Broersma, Fedor V. Fomin, Pim van ’t Hof, Daniël Paulusma

   Pages 44-53

6. Maximum Series-Parallel Subgraph

   • Gruia Călinescu, Cristina G. Fernandes, Hemanshu Kaul

   Pages 54-65

7. Low-Port Tree Representations

   • Shiri Chechik, David Peleg

   Pages 66-76

8. Fully Dynamic Representations of Interval Graphs

   • Christophe Crespelle

   Pages 77-87

9. The Parameterized Complexity of Some Minimum Label Problems

   • Michael R. Fellows, Jiong Guo, Iyad A. Kanj

   Pages 88-99

10. Exact and Parameterized Algorithms for Max Internal Spanning Tree

    • Henning Fernau, Serge Gaspers, Daniel Raible

    Pages 100-111

11. An Exact Algorithm for Minimum Distortion Embedding

    • Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh

    Pages 112-121

12. Sub-coloring and Hypo-coloring Interval Graphs

    • Rajiv Gandhi, Bradford Greening Jr., Sriram Pemmaraju, Rajiv Raman

    Pages 122-132

13. Parameterized Complexity of Generalized Domination Problems

    • Petr A. Golovach, Jan Kratochvíl, Ondřej Suchý

    Pages 133-142

14. Connected Feedback Vertex Set in Planar Graphs

    • Alexander Grigoriev, René Sitters

    Pages 143-153

15. Logical Locality Entails Frugal Distributed Computation over Graphs (Extended Abstract)

    • Stéphane Grumbach, Zhilin Wu

    Pages 154-165

16. On Module-Composed Graphs

    • Frank Gurski, Egon Wanke

    Pages 166-177

17. An Even Simpler Linear-Time Algorithm for Verifying Minimum Spanning Trees

    • Torben Hagerup

    Pages 178-189

18. The k-Disjoint Paths Problem on Chordal Graphs

    • Frank Kammer, Torsten Tholey

    Pages 190-201

19. Local Algorithms for Edge Colorings in UDGs

    • Iyad A. Kanj, Andreas Wiese, Fenghui Zhang

    Pages 202-213

20. Directed Rank-Width and Displit Decomposition

    • Mamadou Moustapha Kanté, Michaël Rao

    Pages 214-225

The 35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2009) took place at Montpellier (France), June 24–26 2009. About 80 computer scientists from all over the world (Australia, Belgium, Canada, China, Czech Republic, France, Germany, Greece, Israel, Japan, Korea, The Netherlands, Norway, Spain, UK, USA) attended the conference. Since1975,ithastakenplace20timesinGermany,fourtimesinTheNeth- lands, twice in Austria, as well as once in Italy, Slovakia, Switzerland, the Czech Republic, France, Norway, and the UK. The conference aims at uniting theory and practice by demonstrating how graph-theoretic concepts can be applied to various areas in computer science, or by extracting new problems from appli- tions. The goal is to present recent research results and to identify and explore directions of future research. The conference is well-balanced with respect to established researchers and young scientists. There were 69 submissions. Each submission was reviewed by at least three, and on average four, Program Committee members. The Committee decided to accept 28 papers. Due to the competition and the limited schedule, some good papers could not be accepted. Theprogramalsoincludedexcellentinvitedtalks:onegivenbyDanielKràlon “AlgorithmsforClassesofGraphswithBoundedExpansion,” the otherbyDavid Eppsteinon“Graph-TheoreticSolutionstoComputationalGeometryProblems.” The proceedings contains two survey papers on these topics.

• Graph
• algorithms
• chordal graphs
• claw-free graphs
• complexity
• computational geometry
• edge colorings
• graph algorithms
• graph partitioning
• k-disjoint graph problem
• minimum spanning trees
• modeling
• planar graphs
• switch graphs
• algorithm analysis and problem complexity
• data structures

• CNRS - LIRMM, Montpellier Cedex 5, France

  Christophe Paul

• LIAFA, case 7014, Université Paris Diderot, Paris Cedex 13, France

  Michel Habib

Policies and ethics