Graph-Theoretic Concepts in Computer Science: 39th International Workshop, WG 2013, Lübeck, Germany, June 19-21, 2013, Revised Papers

by Andreas Brandstädt (Editor), Klaus Jansen (Editor), Rüdiger Reischuk (Editor)

Tree-Like Structures in A Metric Point of View.- Overview of New Approaches for Approximating TSP.- Linear Rank-Width and Linear Clique-Width of Trees.- Threshold-Coloring and Unit-Cube Contact Representation of Graphs.- Rolling Upward Planarity Testing of Strongly Connected Graphs.- Towards a Provably Resilient Scheme for Graph-Based Watermarking.- The Normal Graph Conjecture for Classes of Sparse Graphs.- On the Parameterized Complexity of Computing Graph Bisections.- Fixed-Parameter Tractability and Characterizations of Small Special Treewidth.- The θ5-Graph is a Spanner.- Graphs of Edge-Intersecting Non-splitting Paths in a Towards Hole Representations (Extended Abstract).- Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs.- Equilateral L-Contact Graphs.- Parameterized and Approximation Algorithms for the MAF Problem in Multifurcating Trees.- Linear Separation of Total Dominating Sets in Graphs.- Sparse Square Roots.- Completing Colored Graphs to Meet a Target Property.- Colouring of Graphs with Ramsey-Type Forbidden Subgraphs.- Lower and Upper Bounds for Long Induced Paths in 3-Connected Planar Graphs.- Computing Minimum Cycle Bases in Weighted Partial 2-Trees in Linear Time.- Thickness and Colorability of Geometric Graphs.- The Same Upper Bound for The 2-Page and the Rectilinear Crossing Numbers of the n-Cube.- FPT Is Characterized by Useful Obstruction Sets.- Excluding Graphs as Immersions in Surface Embedded.- OBDD-Based Representation of Interval Graphs.- Tight Upper Bounds for Minimum Feedback Arc Sets of Regular.- A Linear-Time Kernelization for the Rooted k-Leaf Outbranching Problem.- On Retracts, Absolute Retracts, and Folds in Cographs.- Coloring Triangle-Free Rectangular Frame Intersection Graphs with O(log log n) Colors.- On Finding Tucker Submatrices and Lekkerkerker-Boland Subgraphs.- Certifying 3-Edge-Connectivity.- Parameterized Algorithms for Max Colorable Induced Subgraph Problem on Perfect Graphs.- Characterizing and Computing the Structure of Clique Intersections in Strongly Chordal Graphs.- Beyond Knights and Knaves.- Drawing Graphs with Few Arcs.- Connecting Terminals and 2-Disjoint Connected Subgraphs.

452 pages, Paperback

First published October 30, 2013