Graph-Theoretic Concepts in Computer Science: 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, June 25-27, 2014. Revised Selected Papers (Lecture Notes in Computer Science Book 8747)

This book constitutes the thoroughly refereed post-conference proceedings of the 40th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2014, held in Nouan-le-Fuzelier, France, in June 2014. The 32 revised full papers presented were carefully reviewed and selected from 80 submissions. The book also includes two invited papers. The papers cover a wide range of topics in graph theory related to computer science, such as 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; random graphs and models of the web and scale-free networks; and support of these concepts by suitable implementations and applications. Front Matter....Pages I-XI Unifying Duality Theorems for Width Parameters in Graphs and Matroids (Extended Abstract)....Pages 1-14 Distributedly Testing Cycle-Freeness....Pages 15-28 DMVP: Foremost Waypoint Coverage of Time-Varying Graphs....Pages 29-41 Linear Rank-Width of Distance-Hereditary Graphs....Pages 42-55 Vertex Contact Graphs of Paths on a Grid....Pages 56-68 Deciding the Bell Number for Hereditary Graph Properties....Pages 69-80 Boxicity and Separation Dimension....Pages 81-92 Maximal Induced Matchings in Triangle-Free Graphs....Pages 93-104 Independent Set Reconfiguration in Cographs....Pages 105-116 Structural Parameterizations for Boxicity....Pages 117-128 A New Characterization of $$P_k$$ -free Graphs....Pages 129-138 Contact Representations of Planar Graphs: Extending a Partial Representation is Hard....Pages 139-151 The Maximum Labeled Path Problem....Pages 152-163 Minimum Spanning Tree Verification Under Uncertainty....Pages 164-175 Towards the Hanani-Tutte Theorem for Clustered Graphs....Pages 176-188 On Set Expansion Problems and the Small Set Expansion Conjecture....Pages 189-200 Hadwiger Number of Graphs with Small Chordality....Pages 201-213 Recognizing Threshold Tolerance Graphs in $$O(n^2)$$ Time....Pages 214-224 Induced Disjoint Paths in Circular-Arc Graphs in Linear Time....Pages 225-237 Near-Linear Time Constant-Factor Approximation Algorithm for Branch-Decomposition of Planar Graphs....Pages 238-249 Parameterized Directed $$k$$ -Chinese Postman Problem and $$k$$ Arc-Disjoint Cycles Problem on Euler Digraphs....Pages 250-262 Colored Modular and Split Decompositions of Graphs with Applications to Trigraphs....Pages 263-274 Edge Elimination in TSP Instances....Pages 275-286 The Parameterized Complexity of the Rainbow Subgraph Problem....Pages 287-298 Kernelizations for the Hybridization Number Problem on Multiple Nonbinary Trees....Pages 299-311 Graph-TSP from Steiner Cycles....Pages 312-323 A Characterization of Mixed Unit Interval Graphs....Pages 324-335 On the Number of Connected Sets in Bounded Degree Graphs....Pages 336-347 Parameterized Edge Hamiltonicity....Pages 348-359 Polynomial Time Recognition of Squares of Ptolemaic Graphs and 3-sun-free Split Graphs....Pages 360-371 The Maximum Time of 2-Neighbour Bootstrap Percolation: Complexity Results....Pages 372-383 Parameterized Algorithms for Graph Partitioning Problems....Pages 384-395 Between Treewidth and Clique-Width....Pages 396-407 A Polynomial Turing-Kernel for Weighted Independent Set in Bull-Free Graphs....Pages 408-419 Back Matter....Pages 421-422