Tree-Like Structures in Graphs: 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 (Sk(B5-Graph is a Spanner -- Graphs of Edge-Intersecting Non-splitting Paths in a Tree: 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 Both: 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.

This book constitutes the thoroughly refereed proceedings of the 39th International Workshop on Graph Theoretic Concepts in Computer Science, WG 2013, held in L�ubeck, Germany, in June 2013. The 34 revised full papers presented were carefully reviewed and selected from 61 submissions. The book also includes two abstracts. The papers cover a wide range of topics in graph theory related to computer science, such as structural graph theory with algorithmic or complexity applications; design and analysis of sequential, parallel, randomized, parameterized and distributed graph and network algorithms; computational complexity of graph and network problems; computational geometry; graph grammars, graph rewriting systems and graph modeling; graph drawing and layouts; random graphs and models of the web and scale-free networks; and support of these concepts by suitable implementations and applications.