Graph-theoretic concepts in computer science : 36th international workshop, WG 2010, Zarós, Crete, Greece, June 28-30, 2010 ; revised papers

This book constitutes the thoroughly refereed post-conference proceedings of the 36th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2010, held in Zar?s, Crete, Greece, in June 2010. The 28 revised full papers presented together with two invited papers were carefully reviewed and selected from 94 initial submissions. The papers feature original results on all aspects of graph-theoretic concepts in Computer Science, e.g. structural graph theory, sequential, parallel, randomised, parameterized, and distributed graph and network algorithms and their complexity, graph grammars and graph rewriting systems, graph-based modelling, graph-drawing and layout, random graphs, diagram methods, and support of these concepts by suitable implementations - as well as applications of graph-theoretic concepts in Computer Science. Cover......Page 1 Lecture Notes in Computer Science, 6410......Page 2 Graph-Theoretic Concepts in Computer Science......Page 3 ISBN-13 9783642169250......Page 4 Preface......Page 6 The Long Tradition of WG......Page 9 WG 2010 Organization......Page 10 Table of Contents......Page 12 Algorithmic Barriers from Phase Transitions in Graphs......Page 16 Algorithmic Graph Minors and Bidimensionality......Page 17 Introduction......Page 18 Preliminaries......Page 19 Spanning Tree Congestion of Planar Graphs......Page 20 Linear Time Solvability of k-STC for 1 ≤ k ≤ 3......Page 21 Linear Time Solvability of k-STC for Graphs of Bounded Degree......Page 22 Weighted k-STC is NP-Complete for k ≥ 10......Page 23 Unweighted k-STC is NP-Complete for k ≥ 10......Page 27 References......Page 28 Introduction......Page 30 Previous Work......Page 31 Forbidden Subgraph......Page 33 Forbidden Induced Subgraph......Page 34 Forbidden Minor......Page 36 References......Page 39 Introduction......Page 42 Theoretical Framework......Page 43 Partial Orders and Cocomparability Graphs......Page 44 Normal Antipaths on Comparability Graphs......Page 46 The Algorithm......Page 47 Correctness and Time Complexity......Page 49 References......Page 52 Introduction......Page 54 Preliminaries......Page 56 Edge 3-Colorings......Page 57 Total 4-Colorings......Page 59 Lower Bounds for Edge 3-Colorings......Page 60 Dynamic Programming Counting Algorithms......Page 61 References......Page 64 Introduction......Page 66 Preliminaries......Page 68 Stable Flows......Page 71 The Structure of Stable Flows......Page 74 References......Page 77 Introduction......Page 78 4-Coloring for P8-Free Graphs......Page 80 Pre-coloring Extension of 4-Coloring for P7-Free Graphs......Page 83 Pre-coloring Extension of 3-Coloring for Subclasses of P7-Free Graphs......Page 85 Pre-coloring Extension of 3-Coloring for ($P_2$+$P_4$)-Free Graphs......Page 86 Conclusions......Page 88 References......Page 89 Introduction......Page 90 Preliminaries......Page 91 Description of Algorithm MinCutBPG......Page 93 Correctness of Algorithm MinCutBPG......Page 95 Concluding Remarks......Page 100 References......Page 101 Introduction......Page 103 Koivisto's Algorithm: Partitioning into Sets......Page 105 A New Recipe for Capacitated Dominating Set: Combining and Cooking the Ingredients......Page 109 References......Page 114 Introduction......Page 115 Preliminaries and Basic Observations......Page 117 Polynomial-Time Cases of Eulerian Extension......Page 119 Weighted Eulerian Extension on Directed Multigraphs......Page 121 Conclusion......Page 125 References......Page 126 Introduction......Page 127 Preliminaries......Page 129 The Structural Results......Page 130 A Kernelization Algorithm......Page 131 A Linear Size Kernel......Page 133 References......Page 136 Introduction......Page 138 FPT via MSO......Page 140 Dynamic Programming on a Sphere Cut Decomposition......Page 141 Extending Tractability......Page 142 Discrete Milling is Hard for Bounded Pathwidth......Page 146 References......Page 149 Introduction......Page 150 RAC Drawings with One Bend per Edge......Page 152 RAC Drawings with Two Bends per Edge......Page 156 Lower Bound Constructions......Page 159 Concluding Remarks......Page 160 References......Page 161 Introduction......Page 162 Preliminaries and Notation......Page 164 Easy Cases: Steiner Tree, Connected Feedback Vertex Set and Connected Odd Cycle Transversal......Page 165 Colourful Graph Motif......Page 167 Reductions......Page 168 On the Positive Side: Polynomial Kernel for Connected Vertex Cover......Page 170 Conclusions and Open Problems......Page 172 References......Page 173 Introduction......Page 174 Framework......Page 177 Vertex Subset and Vertex Partitioning Problems......Page 178 Boolean-Width is Less than or Equal to Branch-Width......Page 181 Random Graphs......Page 182 References......Page 184 Introduction......Page 186 Preliminaries......Page 188 (p,q)-Cluster Graph Recognition is NP-Complete......Page 189 Polynomial-Time Recognizable (p,q)-Cluster Graphs......Page 190 Polynomial-Time Recognition of (p,2)-Cluster Graphs......Page 191 Polynomial-Time Recognition of (0,q)-Cluster Graphs......Page 192 Polynomial-Time Recognition of (1,3)-Cluster Graphs......Page 194 Concluding Remarks......Page 196 References......Page 197 Introduction......Page 199 Preliminaries......Page 200 (K3,F)-Free Graphs with F Containing an Isolated Vertex......Page 202 Graphs of Bounded Clique-Width......Page 203 Further Results......Page 207 Concluding Remarks and Open Problem......Page 208 References......Page 209 Introduction......Page 211 Preliminaries......Page 213 The Pathwidth-One Vertex Deletion Problem......Page 215 An FPT Algorithm for POVD......Page 216 A Polynomial Kernel for POVD......Page 217 Reduction Rules......Page 218 Correctness and Running time......Page 219 Conclusion......Page 220 References......Page 221 Introduction......Page 223 Model and Basics......Page 225 Asymmetry......Page 227 Exploration with k = 3 Robots......Page 228 Exploration with k=4 Robots......Page 229 Graphs with a Pseudo-neck......Page 230 Graphs with a Neck......Page 231 Exploration with k >4 Odd......Page 233 References......Page 234 Introduction......Page 235 Sampling Digraphs......Page 240 Characterization of Arc-Swap Sequences......Page 242 Sampling within Randomly Chosen Components......Page 244 References......Page 245 Introduction......Page 247 NP-Hardness on a Restricted Graph Class......Page 249 An Outline of the Algorithm......Page 250 Finding Disjoint Unit Interval Vertex Deletion Sets......Page 251 References......Page 257 Introduction......Page 259 Problem Definition and Notation......Page 260 Fixed-Parameter Tractability of APS......Page 261 Outline of the Algorithm......Page 262 Fragmentations and Related Concepts......Page 263 Description of the Algorithm......Page 266 Analysis of the Algorithm......Page 269 References......Page 270 Introduction......Page 271 Definitions and Background......Page 272 Greedy Path Forcing......Page 273 Consequences......Page 277 References......Page 280 Connections between Theta-Graphs, Delaunay Triangulations, and Orthogonal Surfaces......Page 281 Orthogonal Surfaces......Page 282 Delaunay Realizability......Page 283 Our Results......Page 284 Half-$Θ_6-Graph......Page 285 Geodesic Embeddings......Page 286 TD-Delaunay Triangulation......Page 287 Unification of the Concepts......Page 288 Spanner......Page 289 Final Remarks......Page 290 References......Page 291 Introduction......Page 294 Related Work......Page 296 Model and Annotation......Page 297 The Network Structure......Page 298 The Broadcasting Model......Page 299 Analysis of the Algorithm......Page 300 References......Page 305 Introduction......Page 307 Hereditary Properties, Universal Graphs, and Applications......Page 309 Encoding Graphs of Low Obstacle Number......Page 312 Proof of Theorem 1......Page 314 Concluding Remarks......Page 315 References......Page 317 Introduction......Page 319 General Framework......Page 321 Turán Numbers for Graphs and Hypergraphs......Page 322 Property B......Page 323 Strong Coloring......Page 326 References......Page 328 Introduction and Statement of Results......Page 330 Proofs......Page 331 References......Page 337 The Proof of Lemma 2......Page 338 Introduction and Preliminaries......Page 339 Lattice Polyhedra......Page 340 The Left/Right Relation......Page 342 Uppermost Paths and the Path Lattice of an s-t-Plane Graph......Page 343 The Path Lattice of a General Plane Graph......Page 346 A Characterization of s-t-Planar Graphs......Page 348 Conclusion and Outlook......Page 349 References......Page 350 Author Index......Page 352 The 36th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2010) took place in Zar ́ os, Crete, Greece, June 28–30, 2010. About 60 mathematicians and computer scientists from all over the world (Australia, Canada, Czech Republic, France, Germany, Greece, Hungary, Israel, Japan, The Netherlands, Norway, Poland, Switzerland, the UK, and the USA) attended the conference. WG has a long tradition. Since 1975, WG has taken place 21 times in Germany, four times in The Netherlands, twice in Austria, twice in France and once in the Czech Republic, Greece, Italy, Norway, Slovakia, Switzerland, and the UK. WG aims at merging theory and practice by demonstrating how concepts from graph theory can be applied to various areas in computer science, or by extracting new graph theoretic problems from applications. The goal is to presentemergingresearchresultsand to identify and exploredirections of future research.The conference is well-balanced with respect to established researchers and young scientists. There were 94 submissions, two of which where withdrawn before entering the review process. Each submission was carefully reviewed by at least 3, and on average 4.5, members of the Program Committee. The Committee accepted 28 papers, which makes an acceptance ratio of around 30%. I should stress that, due to the high competition and the limited schedule, there were papers that were not accepted while they deserved to be. The 36th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2010) took place in Zarþ os, Crete, Greece, June 28-30, 2010. About 60 mathematicians and computer scientists from all over the world (Australia, Canada, Czech Republic, France, Germany, Greece, Hungary, Israel, Japan, The Netherlands, Norway, Poland, Switzerland, the UK, and the USA) attended the conference. WG has a long tradition. Since 1975, WG has taken place 21 times in Germany, four times in The Netherlands, twice in Austria, twice in France and once in the Czech Republic, Greece, Italy, Norway, Slovakia, Switzerland, and the UK. WG aims at merging theory and practice by demonstrating how concepts from graph theory can be applied to various areas in computer science, or by extracting new graph theoretic problems from applications. The goal is to presentemergingresearchresultsand to identify and exploredirections of future research. The conference is well-balanced with respect to established researchers and young scientists. There were 94 submissions, two of which where withdrawn before entering the review process. Each submission was carefully reviewed by at least 3, and on average 4.5, members of the Program Committee. The Committee accepted 28 papers, which makes an acceptance ratio of around 30%. I should stress that, due to the high competition and the limited schedule, there were papers that were not accepted while they deserved to be 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; graph grammars, graph rewriting systems and graph modeling;