Aims and Scope;  Important Dates;  Registration;  Invited Speakers;  Accepted Papers;  Submission ;  Best Student Paper Award;  Location;  Accommodation;  Program Committee;  Organisation;  Programme;  Sponsors; 

  WG 2008

34th International Workshop on

Graph-Theoretic Concepts

in Computer Science

30 June - 2 July 2008

Durham University, U.K.

     

The LNCS proceedings can be viewed using this LINK

Pictures can now be viewed using this LINK


The 34th International Workshop on Graph-Theoretic Concepts in Computer Science WG 2008 will be held at Durham University from 30th of June to 2nd of July 2008 (ending with lunch on 2nd of July), with  participants expected to arrive on the 29th of June. It continues the series of 33 previous WG's. Since 1975, it took place twenty-one times in Germany, four times in The Netherlands, twice in Austria as well as once in Italy, Slovakia, Switzerland, the Czech Republic, France and in Norway.

Aims and Scope

WG 2008 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 applications. 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. For many years now, the proceedings have been published in the LNCS series of Springer-Verlag. We need the final version of accepted papers approximately two months after the conference.

Papers are solicited describing original results on all aspects of graph-theoretic concepts in Computer Science, e.g. 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 support of these concepts by suitable implementations. The scope of WG includes all applications of graph-theoretic concepts in Computer Science, including data structures, data bases, programming languages, computational geometry, tools for software construction, communications, computing on the web, models of the web and scale-free networks, ad hoc networks, mobile computing, concurrency, computer architectures, VLSI, artificial intelligence, graphics, CAD, operations research, and pattern recognition.


Registration

The registration desk in the reception area of Van Mildert College will be open from Sunday 14:00.
There will be a welcome reception with drinks and snacks in Van Mildert College Sunday evening from 19:00, but there is no dinner on Sunday.

To register for the meeting please use the online registration system by going directly to the registration page or after first reading the booking details.
The registration closes at Wednesday June 25 on 18:00. The registration fee of £300 includes three nights en-suite accommodation, all meals and refreshments throughout the day, and the conference banquet in Durham Castle, as well as all the fees to cover additional costs. For current exchange rates please consult this converter.
A day rate of £220 is applicable to those not requiring accommodation.

Invited Speakers

The following invited speakers have confirmed to give a talk; tentative titles have been added.

Giuseppe Di Battista - Università Roma Tre, Italy
(Un)-Stable Routing in the Internet: a Survey from the Algorithmic Perspective

Leszek Gąsieniec, University of Liverpool, UK
Memory Efficient Graph Exploration

Martin Grohe, Humboldt-Universität zu Berlin, Germany
Algorithmic Meta Theorems

Accepted Papers

The following 30 papers have been selected by the PC for presentation at WG 2008:

Ilia Averbouch, Benny Godlin and Johann Makowsky.
A Most General Edge Elimination Polynomial

Davide Bilò, Luca Forlizzi and Guido Proietti.
Approximating the Metric TSP in Linear Time

Hans L. Bodlaender, Alexander Grigoriev, Nadejda V. Grigorieva and Albert Hendriks.
The Valve Location Problem in Simple Network Topologies

Paul Bonsma and Florian Zickfeld.
A 3/2-Approximation Algorithm for finding Spanning Trees with Many Leaves in Cubic Graphs

Jianer Chen, Iyad Kanj, Jie Meng, Ge Xia and Fenghui Zhang.
On the Pseudo-Achromatic Number Problem

Elad Cohen, Martin Charles Golumbic, Marina Lipshteyn, and Michal Stern.
What is between Chordal and Weakly Chordal Graphs?

Pierluigi Crescenzi, Miriam Di Ianni, Federico Greco, Gianluca Rossi and Paola Vocca.
Making Role Assignment Feasible: A Polynomial-time Algorithm for Computing Ecological Colorings

Marek Cygan and Marcin Pilipczuk.
Faster Exact Bandwidth

Feodor Dragan, Derek Corneil, Ekkehard Koehler and Yang Xiang.
Additive Spanners for Circle Graphs and Polygonal Graphs

Alejandro Estrella-Balderrama, Fabrizio Frati and Stephen Kobourov.
Upward Straight-line Embeddings of Directed Graphs into Point Sets

Jiri Fiala and Petr Golovach.
Complexity of the Packing Coloring Problem of Trees

J. Joseph Fowler, Michael Juenger, Stephen Kobourov and Michael Schulz.
Characterizing Simultaneous Embedding with Fixed Edges

Fabrizio Frati.
A Lower Bound on the Area Requirements of Series-Parallel Graphs

Serge Gaspers, Dieter Kratsch and Mathieu Liedloff.
On Independent Sets and Bicliques in Graphs

Benny Godlin, Tomer Kotek and Johann Makowsky.
Evaluations of Graph Polynomials

Petr Golovach and Yngve Villanger.
Parameterized Complexity for Domination Problems on Degenerate Graphs

Gregory Gutin, Adrian Johnstone, Joseph Reddington, Elizabeth Scott and Anders Yeo.
An Algorithm for finding Input-Output Constrained Convex Sets in an Acyclic Digraph

Pinar Heggernes, Daniel Lokshtanov, Rodica Mihai and Charis Papadopoulos.
Cutwidth of Split Graphs, Threshold Graphs, and Proper Interval Graphs

Vít Jelínek.
The Rank-Width of the Square Grid

Joachim Kneis, Alexander Langer and Peter Rossmanith.
Improved Upper Bounds for Partial Vertex Cover

Pascal Koiran and Klaus Meer.
On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width

Athanassios Koutsonas and Dimitrios M. Thilikos.
Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms

Stephan Kreutzer and Sebastian Ordyniak.
Digraph Decompositions and Monotonicity in Digraph Searching

Dániel Marx and Ildi Schlotter.
Parameterized Graph Cleaning Problems

Xavier Muñoz and Ignasi Sau.
Traffic Grooming in Unidirectional WDM Rings with Bounded Degree Request Graph

Nicolas Nisse and Karol Suchan.
Fast Robber in Planar Graphs

Yahav Nussbaum.
>From a Circular-Arc Model to a Proper Circular-Arc Model

David Richerby and Dimitrios M. Thilikos.
Searching for a Visible, Lazy Fugitive

Siamak Tazari and Matthias Müller-Hannemann.
A Faster Shortest-Paths Algorithm for Minor-Closed Graph Classes

Andreas Wiese and Evangelos Kranakis.
Local Construction and Coloring of Spanners of Location Aware Unit Disk Graphs

Important Dates

Paper submission deadline was March 2, 2008
Notification of acceptance was April 28, 2008
Registration closes at 18:00, June 25, 2008
Conference: 30 June - 2 July, 2008
Participants are expected to arrive on 29th of June. The registration desk in Van Mildert College will be open in the afternoon from 14:00.
There will be a welcome reception with drinks and snacks in Van Mildert College later that day (from 19:00), but the opening of the
workshop is at 8:50 on 30th June, and the first talk starts at 9:00.
The meeting ends with lunch on 2nd of July.

Submission

The paper submission deadline has passed.

Authors are invited to submit an extended abstract in English no longer than 10 pages on letter-size or a4-size paper using at least 11-point font (and preferably LaTeX article style 11pt a4paper). Proofs omitted due to space constraints must be put into an appendix to be read by the program committee members at their discretion. Simultaneous submission to other conferences with published proceedings is not allowed.
Authors who wish to submit a paper must submit a PostScript or PDF file with their paper by using the electronic submission system at:

http://www.easychair.org/conferences/?conf=WG2008

The submission must be received by 23:59 (GMT) on March 2, 2008. Authors unable to submit electronically should contact a co-chair of the Program Committee. Accepted papers are expected to be presented at the conference.

Best Student Paper Award

There is a best student paper award of 500 Euro available. The program committee will judge the submissions and announce the best student paper during the conference dinner in Durham Castle.
The award is sponsored by INFO.RO.

Location

The workshop will be held in Van Mildert College at Durham University. 

Maps and directions on how to get there can be found here.

Accommodation and Venue

Accommodation will also be in Van Mildert College, in en-suite rooms.

Program Committee

Hajo Broersma, Durham University, UK (co-chair)
Artur Czumaj, University of Warwick, UK
Thomas Erlebach, University of Leicester, UK (co-chair)
Mike Fellows, The University of Newcastle, Australia
Fedor V. Fomin, University of Bergen, Norway
Juraj Hromkovic, ETH Zürich, Switzerland
Jan Kratochvil, Charles University, Prague, Czech Republic
Ludek Kucera, Charles University, Prague, Czech Republic
Jan van Leeuwen, Universiteit Utrecht, The Netherlands
Alberto Marchetti-Spaccamela, Sapienza University of Rome, Italy
Hartmut Noltemeier, Universität Würzburg, Germany
Christophe Paul, CNRS, LIRMM, Montpellier, France
Andrzej Pelc, Université du Québec, Canada
Ingo Schiermeyer, TU Bergakademie Freiberg, Germany
Jan Arne Telle, University of Bergen, Norway
Takeaki Uno, National Institute of Informatics (NII), Japan
Dorothea Wagner, University Karlsruhe, Germany
Peter Widmayer, ETH Zürich, Switzerland
Shmuel Zaks, Technion, Haifa, Israel

Local Organisation

The workshop is organised by the Algorithms and Complexity group of
the Department of Computer Science at Durham University,
chaired by Hajo Broersma.

Programme

All the talks take place in the Garrod Room in the Conference Centre of Van Mildert College.


Sunday, June 29
                                      
           From 14:00         Registration in Van Mildert College
           From 19:00         Welcome Reception in Van Mildert College



 Monday, June 30


8:50 - 9:00 Opening


9:00 - 9:50 Invited talk

Memory Efficient Graph Exploration

Leszek Gasieniec


9:50 - 10:15 Parameterized Graph Cleaning Problems

Ildi Schlotter
10:15 - 10:40 Improved Upper Bounds for Partial Vertex Cover

Joachim Kneis


10:40 - 11:00 Coffee/tea


11:00 - 11:25 The Valve Location Problem in Simple Network Topologies

Hans L. Bodlaender
11:25 - 11:50 A Lower Bound on the Area Requirements of Series-Parallel Graphs

Fabrizio Frati
11:50 - 12:15 Characterizing Simultaneous Embedding with Fixed Edges

J. Joseph Fowler
12:15 - 12:40 Approximating the Metric TSP in Linear Time

Davide Bilò


12:40 - 14:15 Lunch


14:15 - 14:40 Faster Exact Bandwidth

Marek Cygan
14:40 - 15:05 On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width

Klaus Meer
15:05 - 15:30 Fast Robber in Planar Graphs

Karol Suchan
15:30 - 15:55 Searching for a Visible, Lazy Fugitive

Dimitrios M. Thilikos


15:55 - 16:15 Coffee/tea


16:15 - 16:40 An Algorithm for finding Input-Output Constrained Convex Sets in an Acyclic Digraph

Elizabeth Scott
16:40 - 17:05 Digraph Decompositions and Monotonicity in Digraph Searching

Sebastian Ordyniak


17:05 - 17:20 Presentation of next year's WG


18:00 -           Dinner

Business/PC meeting







Tuesday, July 1


9:00 - 9:50 Invited talk

(Un)-Stable Routing in the Internet: a Survey from the Algorithmic Perspective

Giuseppe Di Battista


9:50 - 10:15 Local Construction and Coloring of Spanners of Location Aware Unit Disk Graphs

Andreas Wiese
10:15 - 10:40 Additive Spanners for Circle Graphs and Polygonal Graphs

Ekkehard Koehler


10:40 - 11:00 Coffee/tea


11:00 - 11:25 Cutwidth of Split Graphs, Threshold Graphs, and Proper Interval Graphs

Daniel Lokshtanov
11:25 - 11:50 The Rank-Width of the Square Grid

Vít Jelínek
11:50 - 12:15 From a Circular-Arc Model to a Proper Circular-Arc Model

Yahav Nussbaum
12:15 - 12:40 What is between Chordal and Weakly Chordal Graphs?

Marina Lipshteyn


12:40 - 14:15 Lunch


14:15 - 14:40 A 3/2-Approximation Algorithm for finding Spanning Trees with Many Leaves in Cubic Graphs

Paul Bonsma
14:40 - 15:05 On Independent Sets and Bicliques in Graphs

Serge Gaspers
15:05 - 15:30 Parameterized Complexity for Domination Problems on Degenerate Graphs

Yngve Villanger
15:30 - 15:55 Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms

Dimitrios M. Thilikos


15:55 - 16:15 Coffee/tea


16:15 - 16:40 Evaluations of Graph Polynomials

Tomer Kotek
16:40 - 17:05 A Most General Edge Elimination Polynomial

Ilia Averbouch


19:30 -           Conference dinner in Durham Castle







Wednesday, July 2


9:00 - 9:50 Invited talk

Algorithmic Meta Theorems

Martin Grohe


9:50 - 10:15 Upward Straight-line Embeddings of Directed Graphs into Point Sets

Alejandro Estrella-Balderrama
10:15 - 10:40 A Faster Shortest-Paths Algorithm for Minor-Closed Graph Classes

Siamak Tazari


10:40 - 11:00 Coffee/tea


11:00 - 11:25 On the Pseudo-Achromatic Number Problem

Iyad Kanj
11:25 - 11:50 Complexity of the Packing Coloring Problem of Trees

Petr Golovach
11:50 - 12:15 Making Role Assignment Feasible: A Polynomial-time Algorithm for Computing Ecological Colorings

Gianluca Rossi
12:15 - 12:40 Traffic Grooming in Unidirectional WDM Rings with Bounded Degree Request Graph

Ignasi Sau


12:40 - 14:15 Closing and lunch

Sponsors

We gratefully acknowledge the financial support from EPSRC and the LMS.