Physical description 
1 online resource (xx, 430 pages) : illustrations. 
Series 
Lecture Notes in Computer Science, 03029743 ; 8165


LNCS sublibrary. SL 1, Theoretical computer science and general issues 

Lecture notes in computer science ; 8165. 03029743


LNCS sublibrary. SL 1, Theoretical computer science and general issues.


Springer Lecture Notes in Computer Science

Notes 
Includes author index. 
Contents 
TreeLike Structures in Graphs: A Metric Point of View / Feodor F. Dragan  Overview of New Approaches for Approximating TSP / Ola Svensson  Linear RankWidth and Linear CliqueWidth of Trees / Isolde Adler, Mamadou Moustapha Kanté  ThresholdColoring and UnitCube Contact Representation of Graphs / Md. Jawaherul Alam, Steven Chaplick  Rolling Upward Planarity Testing of Strongly Connected Graphs / Christopher Auer, Christian Bachmaier  Towards a Provably Resilient Scheme for GraphBased Watermarking / Lucila Maria Souza Bento, Davidson Boccardo  The Normal Graph Conjecture for Classes of Sparse Graphs / Anne Berry, Annegret Wagler  On the Parameterized Complexity of Computing Graph Bisections / René van Bevern, Andreas Emil Feldmann  FixedParameter Tractability and Characterizations of Small Special Treewidth / Hans L. Bodlaender, Stefan Kratsch. 

Lower and Upper Bounds for Long Induced Paths in 3Connected Planar Graphs / Emilio Di Giacomo, Giuseppe Liotta  Computing Minimum Cycle Bases in Weighted Partial 2Trees in Linear Time / Carola Doerr, G. Ramakrishna  Thickness and Colorability of Geometric Graphs / Stephane Durocher, Ellen Gethner  The Same Upper Bound for Both: The 2Page and the Rectilinear Crossing Numbers of the nCube / Luerbio Faria, Celina M.H. de Figueiredo  FPT Is Characterized by Useful Obstruction Sets / Michael R. Fellows, Bart M.P. Jansen  Excluding Graphs as Immersions in Surface Embedded Graphs / Archontia C. Giannopoulou, Marcin Kamiński  OBDDBased Representation of Interval Graphs / Marc Gillé  Tight Upper Bounds for Minimum Feedback Arc Sets of Regular Graphs / Kathrin Hanauer, Franz J. Brandenburg  A LinearTime Kernelization for the Rooted kLeaf Outbranching Problem / Frank Kammer. 

The θ 5Graph is a Spanner / Prosenjit Bose, Pat Morin, André van Renssen  Graphs of EdgeIntersecting Nonsplitting Paths in a Tree: Towards Hole Representations / Arman Boyacı, Tınaz Ekim, Mordechai Shalom  LinearTime Algorithms for Scattering Number and HamiltonConnectivity of Interval Graphs / Hajo Broersma, Jiří Fiala, Petr A. Golovach  Equilateral LContact Graphs / Steven Chaplick, Stephen G. Kobourov  Parameterized and Approximation Algorithms for the MAF Problem in Multifurcating Trees / Jianer Chen, JiaHao Fan, SingHoi Sze  Linear Separation of Total Dominating Sets in Graphs / Nina Chiarelli, Martin Milanič  Sparse Square Roots / Manfred Cochefert, JeanFrançois Couturier  Completing Colored Graphs to Meet a Target Property / Kathryn Cook, Elaine M. Eschen, R. Sritharan  Colouring of Graphs with RamseyType Forbidden Subgraphs / Konrad K. Dabrowski, Petr A. Golovach. 

On Retracts, Absolute Retracts, and Folds in Cographs / Ton Kloks, YueLi Wang  Coloring TriangleFree Rectangular Frame Intersection Graphs with O(loglogn) Colors / Tomasz Krawczyk, Arkadiusz Pawlik  On Finding Tucker Submatrices and LekkerkerkerBoland Subgraphs / Nathan Lindzey, Ross M. McConnell  Certifying 3EdgeConnectivity / Kurt Mehlhorn, Adrian Neumann  Parameterized Algorithms for Max Colorable Induced Subgraph Problem on Perfect Graphs / Neeldhara Misra, Fahad Panolan, Ashutosh Rai  Characterizing and Computing the Structure of Clique Intersections in Strongly Chordal Graphs / Ragnar Nevries, Christian Rosenke  Beyond Knights and Knaves / Christine T. Cheng, Andrew McConvey  Drawing Graphs with Few Arcs / André Schulz  Connecting Terminals and 2Disjoint Connected Subgraphs / Jan Arne Telle, Yngve Villanger. 
Summary 
This book constitutes the thoroughly refereed proceedings of the 39th International Workshop on Graph Theoretic Concepts in Computer Science, WG 2013, held in Lubeck, 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 scalefree networks; and support of these concepts by suitable implementations and applications. 
Other author 
Brandstädt, Andreas, editor.


Jansen, Klaus, editor.


Reischuk, Rüdiger, editor.


SpringerLink issuing body.

Subject 
Graph theory  Data processing  Congresses.


Computer science  Congresses.


Congresses. 

Electronic books. 

Conference papers and proceedings. 

Electronic books. 

Ebook. 
Variant Title 
WG 2013 
ISBN 
9783642450433 

3642450431 

3642450423 

9783642450426 

9783642450426 
Standard Number 
10.1007/9783642450433 
