Graph-Theoretic Concepts in Computer Science

This book constitutes the thoroughly refereed post-conference proceedings of the 35th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2009, held in Montpellier, France, in June 2009.The 28 revised full papers presented together with two invited papers were carefully reviewed and selected from 69 submissions. The papers feature original results on all aspects of graph-theoretic concepts in Computer Science, e.g. structural graph theory, sequential, parallel, and distributed graph and network algorithms and their complexity, graph grammars and graph rewriting systems, graph-based modeling, graph-drawing and layout, diagram methods, and support of these concepts by suitable implementations. Springer - Graph-Theoretic Concepts in Computer Science (02-2010) (ATTiCA)......Page 0 Preface......Page 4 Conference Organization......Page 5 Table of Contents......Page 8 Introduction......Page 11 Art Gallery Problems......Page 12 Partition into Rectangles......Page 13 Minimum Diameter Clustering......Page 15 Bend Minimization......Page 17 Mesh Stripification......Page 18 Angle Optimization of Tilings......Page 20 Metric Embedding into Stars......Page 21 Conclusions......Page 23 Introduction......Page 27 Graph Decompositions, Graph Minors......Page 28 Grad and Expansion......Page 30 Orientations with Small In-Degree......Page 33 Low Tree-Width and Low-Tree-Depth Coloring......Page 36 Testing Graph Properties......Page 38 $\Sigma$1-Properties......Page 39 First-Order Properties......Page 40 Motivation: Community Structure in Networks......Page 43 Q(G;x,y) as a Graph Polynomial......Page 44 Distinguishing Power......Page 45 Subset Expansion and Definability in Logic......Page 46 The Universality Property of Q( G;x,y)......Page 47 Vertex Eliminations vs Edge Elimination......Page 49 Parameterized Complexity......Page 50 Conclusions and Open Problems......Page 51 Introduction......Page 54 The Two Exact Algorithms......Page 56 Closed Trails of Low Degeneracy and Ordering......Page 57 Branching on Vertices of Low Degree......Page 58 An O*(1.6818n) Time Algorithm That Uses Exponential Space......Page 59 Conclusions......Page 62 Introduction......Page 64 Preliminaries......Page 65 A Local Improvement Algorithm......Page 68 Running Time Analysis......Page 70 Approximation Ratio Analysis......Page 71 Introduction......Page 76 Construction of a Low Port Tree with Cost O(n)......Page 77 Outline of the Algorithm......Page 78 Analysis......Page 82 Introduction......Page 87 Preliminaries......Page 88 Three Representations of Interval Graphs......Page 89 Linear-Time Equivalence of PQ-Representation and MD-Representation......Page 91 Focus on the Key Node......Page 92 Dynamic Characterisation of Interval Graphs......Page 93 Overview of the Algorithm and Complexity......Page 95 Introduction......Page 98 Parameterized Hardness Results......Page 100 Minimum Label Maximum Matching (MLMM)......Page 101 Minimum Label Edge Dominating Set (MLEDS)......Page 106 Concluding Remarks......Page 108 Introduction......Page 110 Observations......Page 112 Reduction Rules......Page 113 The Algorithm......Page 114 Conclusion and Future Research......Page 120 Introduction......Page 122 Preliminaries......Page 123 Exact Algorithm for Distortion......Page 124 Dealing with Many Buckets......Page 125 Dealing with Few Buckets......Page 127 Concluding Remarks and Open Problems......Page 130 Introduction......Page 132 Applications......Page 134 Related Work......Page 135 Partitioning Phase......Page 136 Analysis......Page 137 NP-Completeness......Page 139 An O(logn)-approximation for Hypo-coloring......Page 140 ($ igma, \rho$)-Domination......Page 143 Notation and Overview of Our Results......Page 145 W[1]-Hardness......Page 146 W[1]-Membership......Page 147 Complexity of the ($ igma, \rho$)-Dominating Set of Size at least n-k Problems......Page 149 Complexity for the Case $ igma, \rho \epsilon$ {EVEN,ODD}......Page 150 Complexity of the ($ igma, \rho$)-Dominating Set of Size (at most) k Problem for Sparse Graphs......Page 151 Introduction......Page 153 Insightful Observations......Page 154 FVS and FHS in Planar Graphs with Minimum Degree 3......Page 156 Diameter of Polytopes......Page 159 Approximation Schemes for FHS and Connected FVS......Page 160 Introduction......Page 164 Graphs, First-Order Logic and Locality......Page 166 Distributed Evaluation of FO......Page 168 Bounded Degree Networks......Page 169 Planar Networks......Page 170 Beyond FO Properties......Page 172 Conclusion......Page 173 Introduction......Page 176 Preliminaries......Page 177 Module-Composed Graphs......Page 178 How to Find Module-Sequences......Page 179 Easy Problems on Module-Composed Graphs......Page 181 Characterizations for Independent Module-Composed Graphs......Page 182 How to Find Independent Module-Sequences......Page 184 Easy Problems on Independent Module-Composed Graphs......Page 185 Conclusions......Page 186 Introduction......Page 188 The $\downarrow$ Operation on Sets......Page 190 The High-Level Algorithm......Page 192 Realizing the Set Operations......Page 194 An Implementation in D......Page 196 Introduction......Page 200 The k-Disjoint-Paths Problem......Page 202 Shortest k-Disjoint Paths......Page 204 A Speedup......Page 205 Hardness of the Disjoint-Paths Problem......Page 209 Introduction......Page 212 Definitions and Notations......Page 214 Preliminaries......Page 215 Edge Coloring......Page 216 The Local Distributed Algorithm......Page 219 The Improved Algorithm......Page 222 Introduction......Page 224 Preliminaries......Page 225 Rank-Width of Digraphs......Page 226 Bi-Partitive Families......Page 227 Quotient Graphs......Page 229 Digraphs of GF(4)-Rank-Width 1......Page 231 Concluding Remarks......Page 233 Introduction......Page 236 Bipartite, Planar, Triangle-Free Graphs......Page 238 Global Connectivity......Page 240 Local Connectivity......Page 243 Even Degrees and Eulerian Graphs......Page 244 Acyclic and Almost Acyclic Graphs......Page 245 Introduction and Results......Page 248 Hardness Results......Page 250 Squares of Strongly Chordal Split Graphs......Page 254 Powers versus Girth......Page 255 Conclusion and Open Problems......Page 257 Introduction......Page 260 Reducing the Problem......Page 262 Case $\Delta$=3, C=4......Page 264 Case $\Delta$ ≥ 4 Even......Page 266 General Upper Bound......Page 267 Optimal Construction for Graphs with a Perfect Matching......Page 268 Improved Lower Bounds......Page 269 Conclusions......Page 270 Introduction......Page 272 Preliminaries......Page 273 Complexity......Page 274 Cliques......Page 275 Bounds on the Oriented Injective Chromatic Number......Page 276 Oriented Injective Colourings of Trees......Page 279 Introduction......Page 283 Preliminaries......Page 285 Definition of Chordal Digraphs and First Results......Page 286 Two Classes of Chordal Digraphs......Page 289 Chordal Semi-complete Digraphs......Page 290 Conclusion......Page 293 Introduction......Page 295 A New Intersection Model for Tolerance Graphs......Page 298 A Canonical Representation of Tolerance Graphs......Page 301 Weighted Independent Set Algorithm in O(n2)......Page 303 Conclusions and Further Research......Page 304 Introduction......Page 306 Preliminaries......Page 307 Polynomial-Time Algorithm for Chain Graphs......Page 308 Polynomial-Time Algorithm for Cochain Graphs and Threshold Graphs......Page 312 Hardness Results......Page 313 Introduction......Page 318 Preliminaries......Page 320 d-Domination Games......Page 321 Monotonicity of Domination Games......Page 323 Complexity of Domination Games......Page 325 Games on Hypergraphs and Visible Robbers......Page 327 Introduction......Page 330 Cycles and Paths in Distance Graphs......Page 332 Connectivity and Diameter in Distance Graphs......Page 335 Introduction......Page 339 Preliminaries......Page 340 Tents......Page 341 Edge-Path with Respect to a Hole......Page 342 Shortcuts of a Hole......Page 343 $\tau$-BFS......Page 345 The Algorithm......Page 346 $\tau$-Path......Page 347 Complexity......Page 348 Further Research......Page 349 Introduction......Page 351 Preliminaries......Page 354 Finding Induced Paths of Given Parity......Page 355 Preprocessing the Input Graph G......Page 356 G'' Is Not Perfect......Page 357 G'' Is Perfect......Page 359 Finding Induced Paths of Given Parity from s to t in G......Page 360 Conclusions and Open Problems......Page 361 Author Index......Page 363