This book constitutes the revised papers of the 45th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2019, held in Vall de Núria, Spain, in June 2019.
The 29 full papers presented in this volume were carefully reviewed and selected from 87 submissions. They cover a wide range of areas, aiming at connecting theory and applications by demonstrating how graph-theoretic concepts can be applied in various areas of computer science. Another focus is on presenting recent results and on identifying and exploring promising directions of future research.
Logic and Random Graphs.- Unavoidability and universality of digraphs.-
Parameterized algorithms for geometric graphs via decomposition theorems.-
Subexponential algorithms for variants of homomorphism problem in string
graphs.- The 4-Steiner Root Problem.- Hamiltonicity below Diracs condition.-
Maximum Independent Sets in Subcubic Graphs: New Results.- Cyclewidth and the
Grid Theorem for Perfect Matching Width of Bipartite Graphs.- Local
approximation of the Maximum Cut in regular graphs.- Fixed-parameter
tractability of counting small minimum (S,T)-cuts.- Fast Breadth-First Search
in Still Less Space.- A Turing Kernelization Dichotomy for Structural
Parameterizations of F-Minor-Free Deletion.- Flip distances between graph
orientations.- Graph functionality.- On Happy Colorings, Cuts, and Structural
Parameterizations.- Shortest Reconfiguration of Matchings.- Travelling on
Graphs with Small Highway Dimension.- The Power of Cut-Based Parameters for
Computing Edge Disjoint Paths.- Geometric Representations of Dichotomous
Ordinal Data.- Linear MIM-width of Trees.- Approximating Minimum Dominating
Set on String graphs.- Classified Rank-Maximal Matchings and Popular
Matchings -- Algorithms and Hardness.- Maximum Matchings and Minimum Blocking
Sets in Theta-6 Graphs.- A polynomial-time algorithm for the independent set
problem in $\{P_{10},C_4,C_6\}$-free graphs.- Independent Set Reconfiguration
Parameterized by Modular-Width.- Counting independent sets in graphs with
bounded bipartite pathwidth.- Intersection Graphs of Non-Crossing Paths.-
Reconfiguring Hamiltonian Cycles in L-Shaped Grid Graphs.- Color Refinement,
Homomorphisms, and Hypergraphs.- 3-colorable planar graphs have an
intersection segment representation using 3 slopes.- The Exponential-Time
Complexity of Counting (Quantum) Graph Homomorphisms.- Minimal separators in
graph classes defined by small forbidden induced subgraphs.
