Graph-Theoretic Concepts in Computer Science: 46th International Workshop, WG 2020, Leeds, UK, June 24–26, 2020, Revised Selected Papers

Front Matter ....Pages i-xv
 Combinatorial Bounds for Conflict-Free Coloring on Open Neighborhoods  (Sriram Bhyravarapu, Subrahmanyam Kalyanasundaram)....Pages 1-13
 Guarding Quadrangulations and Stacked Triangulations with Edges  (Paul Jungeblut, Torsten Ueckerdt)....Pages 14-26
 Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space  (Jesper Nederlof, Michał Pilipczuk, Céline M. F. Swennenhuis, Karol Węgrzycki)....Pages 27-39
 Parameterized Inapproximability of Independent Set in H-Free Graphs  (Pavel Dvořák, Andreas Emil Feldmann, Ashutosh Rai, Paweł Rzążewski)....Pages 40-53
 Clique-Width of Point Configurations  (Onur Çağırıcı, Petr Hliněný, Filip Pokrývka, Abhisekh Sankaran)....Pages 54-66
 On the Complexity of Finding Large Odd Induced Subgraphs and Odd Colorings  (Rémy Belmonte, Ignasi Sau)....Pages 67-79
 Knot Diagrams of Treewidth Two  (Hans L. Bodlaender, Benjamin Burton, Fedor V. Fomin, Alexander Grigoriev)....Pages 80-91
 Treewidth Versus Clique Number in Graph Classes with a Forbidden Structure  (Clément Dallard, Martin Milanič, Kenny àtorgel)....Pages 92-105
 Graph Isomorphism Restricted by Lists  (Pavel Klavík, Dušan Knop, Peter Zeman)....Pages 106-118
 Clique-Width: Harnessing the Power of Atoms  (Konrad K. Dabrowski, Tomáš Masařík, Jana Novotná, Daniël Paulusma, Paweł Rzążewski)....Pages 119-133
 Edge Elimination and Weighted Graph Classes  (Jesse Beisegel, Nina Chiarelli, Ekkehard Köhler, Matjaž Krnc, Martin Milanič, Nevena Pivač et al.)....Pages 134-147
 Well-Partitioned Chordal Graphs: Obstruction Set and Disjoint Paths  (Jungho Ahn, Lars Jaffke, O-joung Kwon, Paloma T. Lima)....Pages 148-160
 Plattenbauten: Touching Rectangles in Space  (Stefan Felsner, Kolja Knauer, Torsten Ueckerdt)....Pages 161-173
 Universal Geometric Graphs  (Fabrizio Frati, Michael Hoffmann, Csaba D. Tóth)....Pages 174-186
 Computing Subset Transversals in H-Free Graphs  (Nick Brettell, Matthew Johnson, Giacomo Paesani, Daniël Paulusma)....Pages 187-199
 Feedback Edge Sets in Temporal Graphs  (Roman Haag, Hendrik Molter, Rolf Niedermeier, Malte Renken)....Pages 200-212
 On Flips in Planar Matchings  (Marcel Milich, Torsten Mütze, Martin Pergel)....Pages 213-225
 Degree Distribution for Duplication-Divergence Graphs: Large Deviations  (Alan Frieze, Krzysztof Turowski, Wojciech Szpankowski)....Pages 226-237
 On Finding Balanced Bicliques via Matchings  (Parinya Chalermsook, Wanchote Po Jiamjitrak, Ly Orgo)....Pages 238-247
 Finding Large Matchings in 1-Planar Graphs of Minimum Degree 3  (Therese Biedl, Fabian Klute)....Pages 248-260
 Strong Cliques in Diamond-Free Graphs  (Nina Chiarelli, Berenice Martínez-Barona, Martin Milanič, Jérôme Monnot, Peter Muršič)....Pages 261-273
 Recognizing k-Clique Extendible Orderings  (Mathew Francis, Rian Neogi, Venkatesh Raman)....Pages 274-285
 Linear-Time Recognition of Double-Threshold Graphs  (Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi, Yushi Uno)....Pages 286-297
 Characterization and Linear-Time Recognition of Paired Threshold Graphs  (Yixin Cao, Guozhen Rong, Jianxin Wang)....Pages 298-309
 Drawing Graphs as Spanners  (Oswin Aichholzer, Manuel Borrazzo, Prosenjit Bose, Jean Cardinal, Fabrizio Frati, Pat Morin et al.)....Pages 310-324
 Inserting One Edge into a Simple Drawing Is Hard  (Alan Arroyo, Fabian Klute, Irene Parada, Raimund Seidel, Birgit Vogtenhuber, Tilo Wiedera)....Pages 325-338
 Bitonic st-Orderings for Upward Planar Graphs: The Variable Embedding Setting  (Patrizio Angelini, Michael A. Bekos, Henry Förster, Martin Gronemann)....Pages 339-351
 2.5-Connectivity: Unique Components, Critical Graphs, and Applications  (Irene Heinrich, Till Heller, Eva Schmidt, Manuel Streicher)....Pages 352-363
 Stable Structure on Safe Set Problems in Vertex-Weighted Graphs II –Recognition and Complexity–  (Shinya Fujita, Boram Park, Tadashi Sakuma)....Pages 364-375
 The Linear Arboricity Conjecture for 3-Degenerate Graphs  (Manu Basavaraju, Arijit Bishnu, Mathew Francis, Drimit Pattanayak)....Pages 376-387
 Node Multiway Cut and Subset Feedback Vertex Set on Graphs of Bounded Mim-width  (Bergougnoux Benjamin, Charis Papadopoulos, Jan Arne Telle)....Pages 388-400
 Weighted Additive Spanners  (Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Stephen Kobourov, Richard Spence)....Pages 401-413
Back Matter ....Pages 415-416