# Graph-theoretic concepts in computer science : 39th International Workshop, WG 2013, Lübeck, Germany, June 19-21, 2013, Revised Papers / Andreas Brandstädt, Klaus Jansen, Rüdiger Reischuk (eds.).

##### By: (39th : International Workshop WG (39th : 2013 : Lübeck, Germany)

##### Contributor(s): Brandstädt, Andreas [editor.] | Jansen, Klaus [editor.] | Reischuk, Rüdiger [editor.]

Material type: TextSeries: SerienbezeichnungLecture notes in computer science: 8165.; LNCS sublibrary: Publisher: Heidelberg : Springer, 2013Description: 1 online resource (xx, 430 pages) : illustrationsContent type: text Media type: computer Carrier type: online resourceISBN: 9783642450433; 3642450431; 3642450423; 9783642450426Other title: WG 2013Subject(s): Graph theory -- Data processing -- Congresses | Computer science -- Congresses | Computer science | Graph theory -- Data processing | Engineering & Applied Sciences | Computer Science | Computer Science | Discrete Mathematics in Computer Science | Algorithm Analysis and Problem Complexity | Data Structures | Geometry | Algorithms | Computers | Electronic Data ProcessingGenre/Form: Congress. | Electronic books. | Ebook. | Conference papers and proceedings. Additional physical formats: Printed edition:: No titleDDC classification: 511.5 LOC classification: QA166 | .C66 2013Online resources: Click here to access onlineItem type | Current location | Collection | Call number | Status | Date due | Barcode | Item holds |
---|---|---|---|---|---|---|---|

eBook |
e-Library
Electronic Book@IST |
EBook | Available |

Includes author index.

Tree-Like Structures in Graphs: A Metric Point of View / Feodor F. Dragan -- Overview of New Approaches for Approximating TSP / Ola Svensson -- Linear Rank-Width and Linear Clique-Width of Trees / Isolde Adler, Mamadou Moustapha Kanté -- Threshold-Coloring and Unit-Cube 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 Graph-Based 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 -- Fixed-Parameter Tractability and Characterizations of Small Special Treewidth / Hans L. Bodlaender, Stefan Kratsch.

880-01 Lower and Upper Bounds for Long Induced Paths in 3-Connected Planar Graphs / Emilio Di Giacomo, Giuseppe Liotta -- Computing Minimum Cycle Bases in Weighted Partial 2-Trees in Linear Time / Carola Doerr, G. Ramakrishna -- Thickness and Colorability of Geometric Graphs / Stephane Durocher, Ellen Gethner -- The Same Upper Bound for Both: The 2-Page and the Rectilinear Crossing Numbers of the n-Cube / 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 -- OBDD-Based Representation of Interval Graphs / Marc Gillé -- Tight Upper Bounds for Minimum Feedback Arc Sets of Regular Graphs / Kathrin Hanauer, Franz J. Brandenburg -- A Linear-Time Kernelization for the Rooted k-Leaf Outbranching Problem / Frank Kammer.

On Retracts, Absolute Retracts, and Folds in Cographs / Ton Kloks, Yue-Li Wang -- Coloring Triangle-Free Rectangular Frame Intersection Graphs with O(loglogn) Colors / Tomasz Krawczyk, Arkadiusz Pawlik -- On Finding Tucker Submatrices and Lekkerkerker-Boland Subgraphs / Nathan Lindzey, Ross M. McConnell -- Certifying 3-Edge-Connectivity / 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 2-Disjoint Connected Subgraphs / Jan Arne Telle, Yngve Villanger.

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 scale-free networks; and support of these concepts by suitable implementations and applications.

Online resource; title from PDF title page (SpringerLink, viewed November 18, 2013).

There are no comments for this item.