Graph-Theoretic Concepts in Computer Science: 44th International Workshop, WG 2018, Cottbus, Germany, June 27–29, 2018, Proceedings

Front Matter ....Pages I-XIII
 On Dispersable Book Embeddings  (Jawaherul Md. Alam, Michael A. Bekos, Martin Gronemann, Michael Kaufmann, Sergey Pupyrev)....Pages 1-14
 Characterising AT-free Graphs with BFS  (Jesse Beisegel)....Pages 15-26
 Edge Partitions of Optimal 2-plane and 3-plane Graphs  (Michael A. Bekos, Emilio Di Giacomo, Walter Didimo, Giuseppe Liotta, Fabrizio Montecchiani, Chrysanthi Raftopoulou)....Pages 27-39
 On Minimum Connecting Transition Sets in Graphs  (Thomas Bellitto, Benjamin Bergougnoux)....Pages 40-51
 Recognizing Hyperelliptic Graphs in Polynomial Time  (Jelco M. Bodewes, Hans L. Bodlaender, Gunther Cornelissen, Marieke van der Wegen)....Pages 52-64
 On Directed Feedback Vertex Set Parameterized by Treewidth  (Marthe Bonamy, Łukasz Kowalik, Jesper Nederlof, Michał Pilipczuk, Arkadiusz Socała, Marcin Wrochna)....Pages 65-78
 Optimality Program in Segment and String Graphs  (Édouard Bonnet, Paweł Rzążewski)....Pages 79-90
 Anagram-Free Chromatic Number Is Not Pathwidth-Bounded  (Paz Carmi, Vida Dujmović, Pat Morin)....Pages 91-99
 Tight Lower Bounds for the Number of Inclusion-Minimal st-Cuts  (Alessio Conte, Roberto Grossi, Andrea Marino, Romeo Rizzi, Takeaki Uno, Luca Versari)....Pages 100-110
 Subexponential-Time and FPT Algorithms for Embedded Flat Clustered Planarity  (Giordano Da Lozzo, David Eppstein, Michael T. Goodrich, Siddharth Gupta)....Pages 111-124
 Computing Small Pivot-Minors  (Konrad K. Dabrowski, François Dross, Jisu Jeong, Mamadou Moustapha Kanté, O-joung Kwon, Sang-il Oum et al.)....Pages 125-138
 Saving Probe Bits by Cube Domination  (Peter Damaschke)....Pages 139-151
 Graph Amalgamation Under Logical Constraints  (Mateus de Oliveira Oliveira)....Pages 152-163
 \\(\\forall \\exists \\mathbb {R}\\)-Completeness and Area-Universality  (Michael Gene Dobbins, Linda Kleist, Tillmann Miltzow, Paweł Rzążewski)....Pages 164-175
 Optimal General Matchings  (Szymon Dudycz, Katarzyna Paluch)....Pages 176-189
 Quasimonotone Graphs  (Martin Dyer, Haiko Müller)....Pages 190-202
 Equiangular Polygon Contact Representations  (Stefan Felsner, Hendrik Schrezenmaier, Raphael Steiner)....Pages 203-215
 Temporal Graph Classes: A View Through Temporal Separators  (Till Fluschnik, Hendrik Molter, Rolf Niedermeier, Philipp Zschoche)....Pages 216-227
 Covering a Graph with Nontrivial Vertex-Disjoint Paths: Existence and Optimization  (Renzo Gómez, Yoshiko Wakabayashi)....Pages 228-238
 On the Relation of Strong Triadic Closure and Cluster Deletion  (Niels Grüttemeier, Christian Komusiewicz)....Pages 239-251
 On Perfect Linegraph Squares  (Meike Hatzel, Sebastian Wiederrecht)....Pages 252-265
 On Weak Isomorphism of Rooted Vertex-Colored Graphs  (Lars Jaffke, Mateus de Oliveira Oliveira)....Pages 266-278
 Connected Vertex Cover for \\((sP_1+P_5)\\)-Free Graphs  (Matthew Johnson, Giacomo Paesani, Daniël Paulusma)....Pages 279-291
 Structurally Parameterized d-Scattered Set  (Ioannis Katsikarelis, Michael Lampis, Vangelis Th. Paschos)....Pages 292-305
 Popular Matchings of Desired Size  (Telikepalli Kavitha)....Pages 306-317
 Convexity-Increasing Morphs of Planar Graphs  (Linda Kleist, Boris Klemz, Anna Lubiw, Lena Schlipf, Frank Staals, Darren Strash)....Pages 318-330
 Treedepth Bounds in Linear Colorings  (Jeremy Kun, Michael P. O’Brien, Blair D. Sullivan)....Pages 331-343
 An Improved FPT Algorithm for Independent Feedback Vertex Set  (Shaohua Li, Marcin Pilipczuk)....Pages 344-355
 Construction and Local Routing for Angle-Monotone Graphs  (Anna Lubiw, Debajyoti Mondal)....Pages 356-368
 Characterization and Recognition of Tree 3-Spanner Admissible Directed Path Graphs of Diameter Three  (B. S. Panda, Anita Das)....Pages 369-381
Back Matter ....Pages 383-384