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.
Author(s): Dimitrios M. Thilikos
Series: Lecture Notes in Computer Science - Theoretical Computer Science and General Issues
Publisher: Springer
Year: 2010
Language: English
Pages: 353
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
