February 26, 2018


April 23, 2018


June 27-29, 2018

Final version

July 15, 2018


Tuesday, June 26, 2018

till 18:00 Arrival at Schloss Lübbenau
from 18:30 Welcome reception

Wednesday, June 27, 2018

8:30 ‒ 8:40 Welcome
Session 1 ‒ Chair: Klaus Meer
8:40 ‒ 9:30 Invited lecture by Maria Chudnovsky:
4-coloring graphs with no induced 6-vertex path
9:30 ‒ 9:55 Jelco M. Bodewes, Hans L. Bodlaender, Gunther Cornelissen and Marieke van der Wegen:
Recognizing hyperelliptic graphs in polynomial time
Best Student Paper Award
9:55 ‒ 10:20 Edouard Bonnet and Paweł Rzążewski:
Optimality Program in Segment and String Graphs
Best Paper Award
10:20 ‒ 10:50 Coffee break
Session 2 ‒ Chair: Thomas Erlebach
10:50 ‒ 11:15 Konrad Kazimierz Dabrowski, François Dross, Jisu Jeong, Mamadou Moustapha Kanté, O-Joung Kwon, Sang-Il Oum and Daniel Paulusma:
Computing Small Pivot-Minors
11:15 ‒ 11:40 Meike Hatzel and Sebastian Wiederrecht:
On Perfect Linegraph Squares
11:40 ‒ 12:05 Jawaherul Alam, Michael Bekos, Martin Gronemann, Michael Kaufmann and Sergey Pupyrev:
On Dispersable Book Embeddings
12:05 ‒ 13:15 Lunch break
Session 3 ‒ Chair: Haiko Müller
13:15 ‒ 13:40 Telikepalli Kavitha:
Popular matchings of desired size
13:40 ‒ 14:05 Renzo Gomez and Yoshiko Wakabayashi:
Covering a graph with nontrivial vertex-disjoint paths: existence and optimization
14:05 ‒ 14:30 Szymon Dudycz and Katarzyna Paluch:
Optimal General Matchings
14:30 ‒ 15:00 Coffee break
Session 4 ‒ Chair: Christophe Paul
15:00 ‒ 15:25 Marthe Bonamy, Lukasz Kowalik, Jesper Nederlof, Michał Pilipczuk, Arkadiusz Socala and Marcin Wrochna:
On Directed Feedback Vertex Set parameterized by treewidth
15:25 ‒ 14:05 Shaohua Li and Marcin Pilipczuk:
An improved FPT algorithm for Independent Feedback Vertex Set
15:50 ‒ 16:15 Ioannis Katsikarelis, Michael Lampis and Vangelis Paschos:
Structurally Parameterized d-Scattered Set
16:15 ‒ 16:40 Giordano Da Lozzo, David Eppstein, Michael Goodrich and Siddharth Gupta:
Subexponential-Time and FPT Algorithms for Embedded Flat Clustered Planarity
18:30 ‒ 20:00 Dinner
from 20:00 Business meeting

Thursday, June 28, 2018

Session 5 ‒ Chair: Ekkehard Köhler
8:30 ‒ 9:20 Invited lecture by Martin Skutella:
Flows over time and submodular function minimization
9:20 ‒ 9:45 Paz Carmi, Vida Dujmovic and Pat Morin:
Anagram-Free Chromatic Number is not Pathwidth-Bounded
9:45 ‒ 10:10 Jeremy Kun, Michael P. O'Brien and Blair D. Sullivan:
Treedepth Bounds in Linear Colorings
10:10 ‒ 10:40 Coffee break
Session 6 ‒ Chair: Steven Chaplick
10:40 ‒ 11:05 Anna Lubiw and Debajyoti Mondal:
Construction and Local Routing for Angle-Monotone Graphs
11:05 ‒ 11:30 Michael Bekos, Emilio Di Giacomo, Walter Didimo, Giuseppe Liotta, Fabrizio Montecchiani and Chrysanthi Raftopoulou:
Edge Partitions of Optimal 2-plane and 3-plane Graphs
11:30 ‒ 11:55 Linda Kleist, Boris Klemz, Anna Lubiw, Lena Schlipf, Frank Staals and Darren Strash:
Convexity-Increasing Morphs of Planar Graphs
11:55 ‒ 12:20 Stefan Felsner, Hendrik Schrezenmaier and Raphael Steiner:
Equiangular polygon contact representations
12:20 ‒ 13:30 Lunch break
Session 7 ‒ Chair: Hans L. Bodlaender
13:30 ‒ 13:55 Alessio Conte, Roberto Grossi, Andrea Marino, Romeo Rizzi, Takeaki Uno and Luca Versari:
Tight Lower Bounds for the Number of st-Cuts
13:55 ‒ 14:20 Lars Jaffke and Mateus de Oliveira Oliveira:
On Weak Isomorphism of Rooted Vertex-Colored Graphs
14:20 ‒ 14:45 Peter Damaschke:
Saving Probe Bits by Cube Domination
14:45 ‒ 15:20 Test of Time Award: Burkhard Monien and Ivan Hal Sudborough
Bounding the Bandwith of NP-Complete Problems
16:00 ‒ 18:00 Excursion to the Spreewald
from 18:30 Conference dinner

Friday, June 29, 2018

Session 8 ‒ Chair: Andreas Brandstädt
8:30 ‒ 9:20 Invited lecture by Martin Milanič:
Strong cliques and graph classes
9:20 ‒ 9:45 Jesse Beisegel:
Characterising AT-free Graphs with BFS
9:45 ‒ 10:10 Martin Dyer and Haiko Müller:
Quasimonotone Graphs
10:10 ‒ 10:40 Coffee break
Session 9 ‒ Chair: Derek Corneil
10:40 ‒ 11:05 Matthew Johnson, Daniel Paulusma and Giacomo Paesani:
Connected Vertex Cover for (sP1+P5)-Free Graphs
11:05 ‒ 11:30 Bhawani Panda and Anita Das:
Characterization and Recognition of Tree 3-Spanner admissible Directed Path Graphs of Diameter Three
11:30 ‒ 11:55 Thomas Bellitto and Benjamin Bergougnoux:
On Minimum Connecting Transition Sets in Graphs
11:55 ‒ 12:20 Niels Grüttemeier and Christian Komusiewicz:
On the Relation of Strong Triadic Closure and Cluster Deletion
12:20 ‒ 13:30 Lunch break
Session 10 ‒ Chair: Jan Kratochvíl
13:30 ‒ 13:55 Michael Dobbins, Linda Kleist, Tillmann Miltzow and Paweł Rzążewski:
∀∃ℝ-completeness and area-universality
13:55 ‒ 14:20 Till Fluschnik, Hendrik Molter, Rolf Niedermeier and Philipp Zschoche:
Temporal Graph Classes: A View Through Temporal Separators
14:20 ‒ 14:45 Mateus De Oliveira Oliveira:
Graph Amalgamation under Logical Constraints
from 15:00 Departure



Lübbenau is a town of 18,000 and located about 30 km west of Cottbus. It is called the gate to the Spreewald, a picturesque landscape consisting of more than 200 small canals, which is a biosphere reserve of UNESCO.

Schloss Lübbenau

The conference is hold at Schloss Lübbenau, the residence of the former counts of Lübbenau. Nowadays it is a hotel.

For supporting participants with young kids we can offer child care during the time of the conference talks, if requested.

Travel Information

Getting to Lübbenau

Berlin Schönefeld Airport (SXF) and Berlin Tegel Airport (TXL) are the best options to reach Lübbenau by plane. From that airports you reach Lübbenau train station in at most 1.5 hours by combination of bus and train.
Other airports in the nearby area are Airport Leipzig/Halle (LEJ) and Airport Dresden (DRS). From that airports the train connections take much longer and are more expensive than that from Berlin's airports.

Getting from Lübbenau train station to Schloss Lübbenau

It's 1.3 km or 16 minutes to walk from the train station of Lübbenau till Schloss Lübbenau. You have to walk through the Poststraße, which starts right in front of the station. At the end of the Poststraße you have to go right into the Ehm-Welk-Straße, which leads you directly to Schloss Lübbenau.

Call for papers

44th International Workshop on Graph-Theoretic Concepts in Computer Science

June 27-29, Schloss Lübbenau (near Cottbus), Germany
Submission Deadline: Feb 26, 2018
Notification: April 23, 2018

The WG 2018 conference is the 44th edition of the WG series. It will take place in Schloss Lübbenau in the middle of Spreewald, near Cottbus, Germany. The conference will take place from Wednesday June 27 to Friday June 29, 2018. Participants are expected to arrive in Lübbenau on Tuesday June 26, to join the welcome reception in the evening.

Important Dates

Submission of papers: February 26, 2018
Acceptance notification: April 23, 2018
Conference: June 27-29, 2018
Final version: July 15, 2018

Aims and Scope

WG conferences aim to connect theory and applications by demonstrating how graph-theoretic concepts can be applied in various areas of computer science. The goal is to present recent results and to identify and explore directions for future research. Submitted papers should describe original results in any aspects of graph theory related to computer science, including but not restricted to:

  • design and analysis of sequential, parallel, randomized, parameterized, and distributed graph and network algorithms,
  • structural graph theory with algorithmic or complexity applications,
  • computational complexity of graph and network problems,
  • graph grammars, graph rewriting systems and graph modeling,
  • graph drawing and layouts,
  • computational geometry,
  • computational biology,
  • random graphs and models of the web and scale-free networks, and
  • support of these concepts by suitable implementations and applications.

Submissions and Proceedings

Contributors are invited to submit an extended abstract of at most 12 pages Springer LNCS format including title, abstract, but excluding references, without changes to the settings of margins and vertical spacing, and with numbered pages. Proofs omitted due to space restrictions must be placed in an appendix, to be read by program committee members at their discretion. Simultaneous submission of papers to any other conference with proceedings published or made publicly available, or submitting papers previously accepted for journal publication is not allowed. Invited papers and accepted contributions will be published in the conference proceedings in the Lecture Notes in Computer Science (LNCS) series of Springer-Verlag. Please submit your paper electronically at: EasyChair

Best Paper Award and Best Student Paper Award

Thanks to a generous donation by Springer Verlag, WG 2018 is able to offer awards of 500 Euro for the best paper and the best student paper. The awards will be decided by the program committee. The committee can decide to split the award(s) over multiple papers. Papers eligible for the best student paper can have non-student co-authors, but the main work in a paper that is a candidate for the best student paper award must be done by co-authors that were students at the time of submission, and the award can be received only by such co-authors. It must be indicated at the time of submission whether a paper is candidate for this award.

Invited Speakers

Maria Chudnovsky

Maria Chudnovsky is Professor at the Department of Mathematics of Princeton University. After getting master degrees at Israel Institute of Technology (1999) and Princeton University (2002), she earned her PhD at Princeton in 2003 with her thesis "Berge Trigraphs and Their Applications". After postdoc positions as Veblen Research Instructor at Princeton and as Clay Research Fellow at the Clay Mathematics Institute, she became Assistant Professor in Princeton in 2005. Between 2006 and 2014, she was Professor at Columbia University. Since 2015, she is Professor for Mathematics at Princeton.
Her research interests lie in graph theory and combinatorics, especially in structural graph theory. For the publication "The strong perfect graph theorem" she and her co-authors won the Fulkerson Prize in 2009. Between 2013 and 2017, she was a MacArthur Fellow. She is a member of the editorial board of the Journal of Graph Theory, a member of the scientific advisory boards of both Oberwolfach Research Institute for Mathematics and Banff International Research Station for Mathematical Innovation and Discovery as well as part of the steering committee of the International Workshop on Combinatorial Algorithms.

Martin Skutella

Martin Skutella is Professor for Combinatorial Optimization and Graph Algorithms at TU Berlin. He got his diploma from RWTH Aachen in 1995 and his PhD in 1998 at TU Berlin. His PhD thesis on "Approximation and Randomization in Scheduling" won the Dissertation Award of the German Operations Research Society. After one year as a postdoc in Belgium, he was a visiting professor at the University of Bonn before he returned to Berlin. He was a visiting professor at the MIT, before he was awarded the habilitation at TU Berlin in 2002. In 2003, he accepted a position as senior researcher at the Max-Planck Institute for Informatics in Saarbrücken. In 2004, he was appointed chair of Discrete Optimization at the University of Dortmund. Since 2007, he is MATHEON-Professor at TU Berlin's Institute of Mathematics. In 2015, the Einstein Foundation Berlin awarded him an Einstein Professorship.
His research interests are focused on Combinatorial Optimization and Efficient Algorithms, at the interface between Discrete Mathematics, Theoretical Computer Science, and Operations Research. He is a member of the editorial boards of several international journals. Between 2009 and 2012, he was editor-in-chief of the Notices of the German Mathematical Society, and as such also board member of the German Mathematical Society.

Martin Milanič

Martin Milanič is Associate Professor at the University of Primorska in Koper, Slovenia. After getting his diploma at the University of Ljubljana in 2003, he went to Rutgers University in New Jersey, where he earned his PhD in 2007 with his thesis "Algorithmic Developments and Complexity Results for Finding Maximum and Exact Independent Sets in Graphs". Between 2007 and 2009, he was postdoc researcher in Germany at Bielefeld University. In 2009, he became Assistant Professor and Research Fellow at the University of Primorska. Between 2013 and 2014, he was also a Research Fellow at the Institute of Mathematics, Physics and Mechanics (IMFM) in Ljubljana. Since 2014, he is Associate Professor at Faculty of Mathematics, Natural Sciences and Information Technologies and Senior Research Fellow at the Andrej Marušič Institute of the University of Primorska.
His research interests lie in algorithmic graph theory, the study of independence and domination graph invariants, the structure and characterization of graphs in hereditary classes, and applications of combinatorial optimization and graph theory to computational biology. In 2017 he was awarded a Zois Certificate of Recognition for important achievements in scientific research work in the field of discrete mathematics. He is editorial board member of The Art of Discrete and Applied Mathematics.


Program Committee

  • Therese Biedl (University of Waterloo, Canada)
  • Andreas Brandstädt (Universität Rostock, Germany, co-chair)
  • Kathie Cameron (Wilfrid Laurier University, Waterloo, Canada)
  • Steven Chaplick (Julius-Maximilians-Universität Würzburg, Germany)
  • Derek Corneil (University of Toronto, Canada)
  • Feodor Dragan (Kent State University, USA)
  • Thomas Erlebach (University of Leicester, United Kingdom)
  • Celina de Figueiredo (Universidade Federal do Rio de Janeiro, Brazil)
  • Fedor Fomin (University of Bergen, Norway)
  • Michel Habib (IRIF, CNRS, Université Paris-Diderot, France)
  • Pinar Heggernes (University of Bergen, Norway)
  • Ekkehard Köhler (BTU Cottbus-Senftenberg, Germany, co-chair)
  • Jan Kratochvíl (Charles University, Prague, Czech Republic)
  • Dieter Kratsch (Université de Lorraine, Metz, France)
  • Ross McConnell (Colorado State University, Fort Collins, USA)
  • Klaus Meer (BTU Cottbus-Senftenberg, Germany, co-chair)
  • Petra Mutzel (TU Dortmund, Germany)
  • Christophe Paul (LIRMM, CNRS, Université de Montpellier, France)
  • Dieter Rautenbach (Universität Ulm, Germany)
  • Ignasi Sau (LIRMM, CNRS, Université de Montpellier, France)
  • Oliver Schaudt (RWTH Aachen, Germany)
  • Dimitrios M. Thilikos (LIRMM, CNRS, Université de Montpellier, France, and National and Kapodistrian University of Athens, Greece)
  • Annegret Wagler (Université Clermont Auvergne, Clermont-Ferrand, France)

Local Organizing Committee

  • Jesse Beisegel
  • Carolin Denkert
  • Romain Gengler
  • Diana Hübner
  • Uwe Jähnert
  • Karla Kersten
  • Ekkehard Köhler
  • Klaus Meer
  • Robert Scheffler
  • Martin Strehler


Invited papers and accepted contributions will be published in the conference proceedings in the Lecture Notes in Computer Science (LNCS) series of Springer-Verlag. Please adhere to the following guidelines.

  • Submit an extended abstract of at most 12 pages including title, abstract, but excluding references.
  • Use the Springer LNCS format. You can find the required class files in this archive.
  • Do not change the settings of margins and vertical spacing, and use numbered pages.
  • Proofs omitted due to space restrictions must be placed in an appendix, to be read by program committee members at their discretion.
  • Simultaneous submission of papers to any other conference with proceedings published or made publicly available, or submitting papers previously accepted for journal publication is not allowed.
  • It must be indicated at the time of submission whether a paper is candidate for the best student paper award. (Papers eligible for the best student paper can have non-student co-authors, but the main work in a paper that is a candidate for the best student paper award must be done by co-authors that were students at the time of submission, and the award can be received only by such co-authors.)

The Submission Deadline (Feb 26, 2018) has passed.


The registration prices below include the conference registration fee, the proceedings, meals, the conference dinner and the excursion. We have discount prices for students, and there is also an option to have further tickets for the dinner including the excursion. The registration fee does not include accommodation. You have to book it yourself, but we have special rates at two hotels until May 16 (for further information see below).
We prefer registration via bank transfer, but registration using a credit card (Mastercard or Visa) is also possible. The details are given to you after your registration.

Prices in EUR


Additional Ticket
(dinner, excursion)
Early bird (until May 16) 275 175 60
Late registration (from May 17) 350 250 60

Registration closed


As Lübbenau is a popular summer resort, there is a contingent of rooms with special prizes reserved for the participants of WG at Schloss Lübbenau and the Spreewaldeck until May 16. If you wish to book a room at one of these hotels, then please register to the conference first. After your successful registration, you will receive a code word. To book one of the reserved rooms, you will need to mention this code word via email or telephone during the booking process. Please note that the reserved rooms cannot be booked through the hotels web interface!
If you would like to share a room with another participant, we can help you to find a room mate. Just write an email to the conference organizers (wg2018 (at) lists.b-tu.de) and we will try to match the requests.

Schloss Lübbenau

Our conference venue "Schloss Lübbenau" is also a hotel. The hotel offers single and double rooms. Breakfast buffet and usage of the exclusive sauna area of the hotel are included in the prices.


The hotel "Spreewaldeck" is a ten minute walk away from the conference venue. The hotel is family-operated. The breakfast buffet is included in the prices.


For questions about the conference or the website contact the organizers via wg2018 (at) lists.b-tu.de