Sponsors

Program

A preliminary program is available here.

Tuesday, June 20, 2017

14.00 ‒ 18.00 Arrival: shuttle service from Heeze Train station to Kapellerput
18.30 ‒ 21.00 Welcome reception and light food

Wednesday, June 21, 2017

7.00 Start breakfast
8.40 ‒ 8.50 Welcome
8.50 ‒ 9.40 Invited Lecture by Petra Mutzel:
Crossing minimization in graph drawing
Session 1. Chair: Hans Bodlaender
9.40 ‒ 10.05 O-Joung Kwon, Michał Pilipczuk and Sebastian Siebertz:
On low rank-width colorings
10.05 ‒ 10.30 Konrad Dabrowski, Vadim Lozin and Daniël Paulusma:
Clique-width and well-quasi ordering of triangle-free graph classes
10.30 ‒ 11.00 Coffee break
Session 2. Chair: Haiko Müller
11.00 ‒ 11.25 Petr Golovach, Pinar Heggernes, Dieter Kratsch, Paloma Lima and Daniel Paulusma:
Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2
11.25 ‒ 11.50 Guillaume Ducoffe:
Finding cut-vertices in the square roots of a graph
11.50 ‒ 12.15 Gregor Hültenschmidt, Philipp Kindermann, Wouter Meulemans and André Schulz:
Drawing planar graphs with few geometric primitives
12.15 Lunch
Session 3. Chair: Petr Golovach
13.45 ‒ 14.10 Patrizio Angelini, Michael Bekos, Franz Brandenburg, Giordano Da Lozzo, Giuseppe Di Battista,
Walter Didimo, Giuseppe Liotta, Fabrizio Montecchiani and Ignaz Rutter:
On the relationship between k-planar and k-quasi planar graphs
14.10 ‒ 14.35 Jean Cardinal, Stefan Felsner, Tillmann Miltzow, Casey Tompkins and Birgit Vogtenhuber:
Intersection graphs of rays and grounded segments
14.35 ‒ 15.00 Hendrik Schrezenmaier:
Homothetic triangle contact representations
15.00 ‒ 15.30 Coffee Break
Session 4. Chair: Petra Mutzel
15.30 ‒ 15.55 Julien Baste, Dieter Rautenbach and Ignasi Sau:
Uniquely restricted matchings and edge colorings
15.55 ‒ 16.20 Maria Chudnovsky, Oliver Schaudt, Sophie Spirkl, Maya Stein and Mingxian Zhong:
Approximately coloring graphs without long induced paths
16.20 ‒ 16.45 Rémy Belmonte, Michael Lampis and Valia Mitsou:
Defective coloring on classes of perfect graphs
16.45 ‒ 17.10 Oliver Schaudt and Fabian Senger:
The parameterized complexity of the equidomination problem
18.30 Dinner
20.00 Meeting of Steering and Program Committees
Free evening for participants

Thursday, June 22, 2017

7.00 Start breakfast
8.30 ‒ 9.20 Invited Lecture by Remco van der Hofstad:
Counting graphs and null models of complex networks: the configuration model and some extensions
Session 5. Chair: Ekkehard Köhler
9.20 ‒ 9.45 Yijia Chen, Martin Grohe and Bingkai Lin:
The hardness of embedding grids and walls
9.45 ‒ 10.10 Till Fluschnik, Meike Hatzel, Steffen Härtlein, Hendrik Molter and Henning Seidler:
The minimum shared edges problem on grid-like graphs
10.10 ‒ 10.40 Coffee break
Session 6. Chair: Michał Pilipczuk
10.40 ‒ 11.05 Julien Baste, Marc Noy and Ignasi Sau:
On the number of labeled graphs of bounded treewidth
11.05 ‒ 11.30 Akanksha Agrawal, Daniel Lokshtanov and Amer Mouawad:
Critical node cut parameterized by treewidth and solution size is W[1]-hard
11.30 ‒ 11.55 Dušan Knop, Martin Koutecky, Tomáš Masařík and Tomáš Toufar:
Simplified algorithmic metatheorems beyond MSO: Treewidth and neighborhood diversity
11.55 ‒ 12.20 Ágnes Cseh and Jannik Matuschke:
New and simple algorithms for stable flow problems
12.20 Lunch
Session 7. Chair: Erik Jan van Leeuwen
13.30 ‒ 13.55 Vadim Lozin, Dmitriy Malyshev, Raffaele Mosca and Victor Zamaraev:
New results on weighted independent domination
13.55 ‒ 14.20 Patrizio Angelini and Michael Bekos:
Hierarchical partial planarity
14.20 ‒ 14.55 Serge Gaspers and Shenwei Huang:
Linearly χ-bounding (P6,C4)-free graphs
14.55 ‒ 15.20 Manuel Aprile, Yuri Faenza, Samuel Fiorini, Tony Huynh and Marco Macchia:
Extension complexity of stable set polytopes of bipartite graphs
15.45 ‒ 18.00 Bicycle trip
18.30 Conference meal (bbq)
Award ceremony for the best paper and the best student paper

Friday, June 23, 2017

7.00 Start breakfast
8.30 ‒ 9.20 Invited Lecture by Fedor Fomin:
Minimal separators and their algorithmic applications
Session 8. Chair: Bart Jansen
9.20 ‒ 9.45 Vicente Acuña, Roberto Grossi, Giuseppe Italiano, Leandro De Lima, Romeo Rizzi,
Gustavo Sacomoto, Marie-France Sagot and Blerina Sinaimeri:
On bubble generators in directed graphs
9.45 ‒ 10.10 Ademir Hujdurović, Edin Husić, Martin Milanic, Romeo Rizzi and Alexandru I. Tomescu:
The minimum conflict-free row split problem revisited
10.10 ‒ 10.40 Coffee break
Session 9. Chair: Fedor Fomin
10.40 ‒ 11.05 Tomasz Krawczyk and Bartosz Walczak:
Extending partial representations of trapezoid graphs
11.05 ‒ 11.30 Steven Chaplick, Martin Töpfer, Jan Voborník and Peter Zeman:
On H-topological intersection graphs
11.30 ‒ 11.55 Pallavi Jain, Jayakrishnan M, Fahad Panolan and Abhishek Sahu:
Mixed dominating set: A parameterized perspective
11.55 ‒ 12.20 Nicolas Bousquet and Marc Heinrich:
Computing maximum cliques in B-EPG graphs
12.20 Lunch
Session 10. Chair: Daniel Paulusma
13.30 ‒ 13.55 Manuel Lafond:
On strongly chordal graphs that are not leaf powers
13.55 ‒ 14.20 Nicolas Bousquet and Marthe Bonamy:
Token sliding on chordal graphs
14.20 ‒ 14.55 Petr Golovach, Dieter Kratsch, Mathieu Liedloff and Mohamed Yosri Sayadi:
Enumeration and maximum number of maximal irredundant sets for chordal graphs
15.15 Shuttle service to Eindhoven

Download program (pdf)

About our invited speakers

Fedor V. Fomin

Fedor Fomin received his Masters (1992) and PhD (1997) from the Faculty of Mathematics and Mechanics at St. Petersburg State University. Since 2002, Fomin has been a professor of Algorithms in the Department of Informatics at the University of Bergen. He is a member of Editorial Boards of Algorithmica, SIAM J. Discrete Mathematics, Information and Computation, Journal of Discrete Algorithms, and Theoretical Computer Science. He chaired Program Committees of ICALP 2013, SWAT 2012, IWPEC 2009 and WG 2006.

Remco van der Hofstad

Remco van der Hofstad is full professor in probability at Eindhoven University of Technology and acting scientific director of Eurandom, the institute in stochastics located on the Eindhoven campus. He received his PhD at the University of Utrecht in 1997, under the supervision of Frank den Hollander and Richard Gill, and worked at McMaster University in Hamilton, Canada, and Delft University of Technology. Remco received the Prix Henri Poincare 2003 jointly with Gordon Slade, the Rollo Davidson Prize 2007, and is a laureate of the `Innovative Research VIDI Scheme' 2003 and `Innovative Research VICI Scheme' 2008. He is also one of the 11 co-applicants of the Gravitation program NETWORKS . Remco is acting spokesman for the Dutch Mathematics platform `Platform Wiskunde Nederland' and editor-in- chief of the `Network Pages’, an interactive website on networks for a broad audience.

Petra Mutzel

Petra Mutzel is Professor for Algorithm Engineering at TU Dortmund. She earned her diploma in 1990 from the University of Augsburg in Mathematics, her doctorate in Computer Science from the University of Cologne in 1994, and her habilitation in 1999 from the Max Planck Institute for Informatics. She held a professorship for Algorithms and Data Structures at Vienna University of Technology beginning in 1999 before moving to TU Dortmund in 2004. She is a member of various Editorial boards including the ACM Journal on Experimental Algorithms, the Journal for Graph Algorithms and Applications (JGAA), Mathematical Programming Computation, and EURO Journal on Computational Optimization. She is in the Steering Committee of ALENEX and of WALCOM. Jointly with Michael Jünger she has co-edited the book Graph Drawing Software, which has been initiated at the International Symposium on Graph Drawing in Vienna in 2001. Petra's research interests are in graph algorithms and combinatorial optimization triggered by applications. She has made contributions in graph drawing and visualization, network design, cheminformatics, physics, and computational biology.

Venue

Kapellerput Conference Hotel, Heeze

The hotel is located in a friendly environment, in a small town called Heeze, southwest of Eindhoven. The surrounding woods are great for short walks and relaxing.

Food

The registration fee includes all meals during the conference: breakfast, (dutch) lunch, and a plentiful dinner, as well as refreshments during breaks.

Travel

Getting to Eindhoven

Eindhoven airport serves mostly cheaper airlines from various European destinations. From the airport, you can get to Eindhoven Central station by bus 10, 400 or 401 in approximately 25 minutes. The second best option is to fly to Amsterdam Schiphol airport: there is a direct InterCity train from Schiphol to Eindhoven. Other nearby options include Dusseldorf and Brussels, as well as the smaller airports in Rotterdam and Maastricht.

Getting to Heeze

The best way to get to Heeze is by train from Eindhoven central station. There is a train every 30 minutes, and the travel time is 9 minutes. Transportation will be arranged from Heeze train station to the hotel by the organizers.

Getting from Heeze (train station) to Kapellerput

On Tuesday, June 13th from 14:00-18:00 a shuttle service between Heeze train station to Kappellerput is arranged. The van will have a sign in front stating `WG 2017’.

If you plan to arrive at a different time, the following options exist.

  1. Take Hermes bus 266 in the direction Deurne and get off at `Kapellerput, Heeze’. Walk 10 minutes to reach the hotel.
  2. Take Hermes bus 258 in the direction Maarheeze Marishof and get off at `Kempenhaeghe, Heeze’. It is a 12 minute walk from this bus stop to the hotel.
  3. Call a taxi at +31 40 842 33 33 (approximate cost: 10€).

Domestic travel in The Netherlands

For travel planning, you can use Google Maps or 9292. We suggest using these planners even for routes suggested here because the train schedules and optimal routes often change due to construction work.

In the Netherlands, paper tickets for single journeys are available from ticket machines at train stations and from the bus driver on buses. Note that there is an extra charge of 0.50 EUR per paper ticket, so if you plan to travel a little more, consider buying an anonymous OV-chipkaart.

Airport Min. travel time Route (details on tickets below)
Amsterdam (AMS) 1:30 Train, direct connection to Eindhoven (every 30 min., travel time 1:29)
Eindhoven (EIN) 0:25 Bus 400 or 401 to Eindhoven central station (every 5-10 min., travel time 0:21 to 0:26)
Rotterdam (RTM) 1:30 Bus 33 every 15 min., travel time 0:22 to Rotterdam central station, then train every 30 min. to Eindhoven, (travel time 1:03)
Maastricht (MST) 1:30 Bus 30 to Beek-Elsloo train station (every 30 min, travel time 14 min), then train to Heeze changing twice in Roermond and Weert (travel time 1:12)
Düsseldorf (DUS) 1:40 (bus) Direct IC bus to Eindhoven (once per hour)
Brussels (BRU) 2:30 Train to Eindhoven, changing twice in Roosendaal, and Tilburg (once per hour)

Registration

The below registration prices include the conference registration fee, the proceedings, accommodation from June 20 till June 23, meals, some drinks, and the excursion. We have discount prices for students, and there is also an option to have a non-participating partner come along (accommodated in a room shared with the participant).
Note that there is a limited amount of rooms, so it is advisable to register soon.

Prices in EUR Regular Student Non-participant
Early bird (until 15 May) 700 450 500
Regular (from 16 May) 800 550 500

Register

Call for papers

43rd International Workshop on Graph-Theoretic Concepts in Computer Science

June 21-23, Heeze (near Eindhoven), the Netherlands
Submission Deadline: Feb 27, 2017, 23:59 (Anywhere on Earth)
Notification: April 24, 2017

The WG 2017 conference is the 43rd edition of the WG series. It will take place in hotel Kapellerput in Heeze, near Eindhoven, the Netherlands. The conference will be from Wednesday June 21 to Friday June 23, 2017. Participants are expected to arrive in Heeze on Tuesday, June 20, where we will have a welcome reception in the evening.

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.

Best Paper Award and Best Student Paper Award

Thanks to a generous donation by Springer Verlag, WG 2017 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.

Important Dates

Submission of papers: February 27, 2017, 23:59 (Anywhere on Earth)
Acceptance notification: April 24, 2017
Conference: June 21-23, 2017
Final version: July 31, 2017

Invited Speakers

  • Fedor V. Fomin
  • Remco van der Hofstad
  • Petra Mutzel

Program Committee

  • Hans L. Bodlaender (Eindhoven and Utrecht, chair)
  • Gerhard J. Woeginger (Aachen, chair)
  • René van Bevern (Novosibirsk)
  • Andreas Brandstädt (Rostock)
  • Bart M. P. Jansen (Eindhoven)
  • Iyad Kanj (Chicago)
  • Mamadou M. Kanté (Aubiere)
  • Michael Kaufmann (Tübingen)
  • Eun Jung Kim (Paris)
  • Christian Komusiewicz (Jena)
  • Stefan Kratsch (Bonn)
  • Asaf Levin (Haifa)
  • Haiko Müller (Leeds)
  • Sang-il Oum (Daejeon)
  • Felix Reidl (Raleigh)
  • Saket Saurabh (Chennai and Bergen)
  • Pascal Schweitzer (Aachen)
  • Jan Arne Telle (Bergen)
  • Ioan Todinca (Orleans)
  • Dimitrios M. Thilikos (Athens and Montpellier)

Organizing Committee

  • Mark de Berg
  • Hans Bodlaender (chair)
  • Bart Jansen
  • Sándor Kisfaludi-Bak
  • Jesper Nederlof
  • Tom van der Zanden

Contact Information

h.l.bodlaender (at) tue.nl

Submissions

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 27, 2017, 23:59 Anywhere on Earth) has passed.

Contact

If you have questions, please contact Hans Bodlaender (h.l.bodlaender (at) tue.nl)

For questions about the website, contact Sándor Kisfaludi-Bak (s.kisfaludi.bak (at) tue.nl)