Graph-Theoretic Concepts in Computer Science: 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017, Revised Selected Papers

Front Matter ....Pages I-XIII
 Counting Graphs and Null Models of Complex Networks: Configuration Model and Extensions  (Remco van der Hofstad)....Pages 1-17
 On Bubble Generators in Directed Graphs  (Vicente Acuña, Roberto Grossi, Giuseppe F. Italiano, Leandro Lima, Romeo Rizzi, Gustavo Sacomoto et al.)....Pages 18-31
 Critical Node Cut Parameterized by Treewidth and Solution Size is W[1]-Hard  (Akanksha Agrawal, Daniel Lokshtanov, Amer E. Mouawad)....Pages 32-44
 Hierarchical Partial Planarity  (Patrizio Angelini, Michael A. Bekos)....Pages 45-58
 On the Relationship Between k-Planar and k-Quasi-Planar Graphs  (Patrizio Angelini, Michael A. Bekos, Franz J. Brandenburg, Giordano Da Lozzo, Giuseppe Di Battista, Walter Didimo et al.)....Pages 59-74
 Extension Complexity of Stable Set Polytopes of Bipartite Graphs  (Manuel Aprile, Yuri Faenza, Samuel Fiorini, Tony Huynh, Marco Macchia)....Pages 75-87
 On the Number of Labeled Graphs of Bounded Treewidth  (Julien Baste, Marc Noy, Ignasi Sau)....Pages 88-99
 Uniquely Restricted Matchings and Edge Colorings  (Julien Baste, Dieter Rautenbach, Ignasi Sau)....Pages 100-112
 Defective Coloring on Classes of Perfect Graphs  (Rémy Belmonte, Michael Lampis, Valia Mitsou)....Pages 113-126
 Token Sliding on Chordal Graphs  (Marthe Bonamy, Nicolas Bousquet)....Pages 127-139
 Computing Maximum Cliques in \(B_2\)-EPG Graphs  (Nicolas Bousquet, Marc Heinrich)....Pages 140-152
 Intersection Graphs of Rays and Grounded Segments  (Jean Cardinal, Stefan Felsner, Tillmann Miltzow, Casey Tompkins, Birgit Vogtenhuber)....Pages 153-166
 On H-Topological Intersection Graphs  (Steven Chaplick, Martin Töpfer, Jan Voborník, Peter Zeman)....Pages 167-179
 The Hardness of Embedding Grids and Walls  (Yijia Chen, Martin Grohe, Bingkai Lin)....Pages 180-192
 Approximately Coloring Graphs Without Long Induced Paths  (Maria Chudnovsky, Oliver Schaudt, Sophie Spirkl, Maya Stein, Mingxian Zhong)....Pages 193-205
 New and Simple Algorithms for Stable Flow Problems  (Ágnes Cseh, Jannik Matuschke)....Pages 206-219
 Clique-Width and Well-Quasi-Ordering of Triangle-Free Graph Classes  (Konrad K. Dabrowski, Vadim V. Lozin, Daniël Paulusma)....Pages 220-233
 Finding Cut-Vertices in the Square Roots of a Graph  (Guillaume Ducoffe)....Pages 234-248
 The Minimum Shared Edges Problem on Grid-Like Graphs  (Till Fluschnik, Meike Hatzel, Steffen Härtlein, Hendrik Molter, Henning Seidler)....Pages 249-262
 Linearly \(\chi \)-Bounding \((P_6,C_4)\)-Free Graphs  (Serge Gaspers, Shenwei Huang)....Pages 263-274
 Algorithms for Outerplanar Graph Roots and Graph Roots of Pathwidth at Most 2  (Petr A. Golovach, Pinar Heggernes, Dieter Kratsch, Paloma T. Lima, Daniël Paulusma)....Pages 275-288
 Enumeration and Maximum Number of Maximal Irredundant Sets for Chordal Graphs  (Petr A. Golovach, Dieter Kratsch, Mathieu Liedloff, Mohamed Yosri Sayadi)....Pages 289-302
 The Minimum Conflict-Free Row Split Problem Revisited  (Ademir Hujdurović, Edin Husić, Martin Milanič, Romeo Rizzi, Alexandru I. Tomescu)....Pages 303-315
 Drawing Planar Graphs with Few Geometric Primitives  (Gregor Hültenschmidt, Philipp Kindermann, Wouter Meulemans, André Schulz)....Pages 316-329
  Mixed Dominating Set: A Parameterized Perspective  (Pallavi Jain, M. Jayakrishnan, Fahad Panolan, Abhishek Sahu)....Pages 330-343
 Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity  (Dušan Knop, Martin Koutecký, Tomáš Masařík, Tomáš Toufar)....Pages 344-357
 Extending Partial Representations of Trapezoid Graphs  (Tomasz Krawczyk, Bartosz Walczak)....Pages 358-371
 On Low Rank-Width Colorings  (O-joung Kwon, Michał Pilipczuk, Sebastian Siebertz)....Pages 372-385
 On Strongly Chordal Graphs That Are Not Leaf Powers  (Manuel Lafond)....Pages 386-398
 New Results on Weighted Independent Domination  (Vadim Lozin, Dmitriy Malyshev, Raffaele Mosca, Viktor Zamaraev)....Pages 399-411
 The Parameterized Complexity of the Equidomination Problem  (Oliver Schaudt, Fabian Senger)....Pages 412-424
 Homothetic Triangle Contact Representations  (Hendrik Schrezenmaier)....Pages 425-437
Back Matter ....Pages 439-440