Skip to main content
SpringerLink
Log in
Book cover

Graph-Theoretic Concepts in Computer Science

44th International Workshop, WG 2018, Cottbus, Germany, June 27–29, 2018, Proceedings

  • Conference proceedings
  • © 2018

Overview

Editors:
  1. Andreas Brandstädt

    1. Universität Rostock, Rostock, Germany

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Ekkehard Köhler

    1. Brandenburgische Technische Universität Cottbus-Senftenberg, Cottbus, Germany

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Klaus Meer

    1. Brandenburgische Technische Universität Cottbus-Senftenberg, Cottbus, Germany

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 11159)

Part of the book sub series: Theoretical Computer Science and General Issues (LNTCS)

Included in the following conference series:

Conference proceedings info: WG 2018.

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (30 papers)

  1. Front Matter

    Pages I-XIII
    Download chapter PDF

  2. On Dispersable Book Embeddings

    • Jawaherul Md. Alam, Michael A. Bekos, Martin Gronemann, Michael Kaufmann, Sergey Pupyrev
    Pages 1-14

  3. Characterising AT-free Graphs with BFS

    • Jesse Beisegel
    Pages 15-26

  4. Edge Partitions of Optimal 2-plane and 3-plane Graphs

    • Michael A. Bekos, Emilio Di Giacomo, Walter Didimo, Giuseppe Liotta, Fabrizio Montecchiani, Chrysanthi Raftopoulou
    Pages 27-39

  5. On Minimum Connecting Transition Sets in Graphs

    • Thomas Bellitto, Benjamin Bergougnoux
    Pages 40-51

  6. Recognizing Hyperelliptic Graphs in Polynomial Time

    • Jelco M. Bodewes, Hans L. Bodlaender, Gunther Cornelissen, Marieke van der Wegen
    Pages 52-64

  7. On Directed Feedback Vertex Set Parameterized by Treewidth

    • Marthe Bonamy, Łukasz Kowalik, Jesper Nederlof, Michał Pilipczuk, Arkadiusz Socała, Marcin Wrochna
    Pages 65-78

  8. Optimality Program in Segment and String Graphs

    • Édouard Bonnet, Paweł Rzążewski
    Pages 79-90

  9. Anagram-Free Chromatic Number Is Not Pathwidth-Bounded

    • Paz Carmi, Vida Dujmović, Pat Morin
    Pages 91-99

  10. Tight Lower Bounds for the Number of Inclusion-Minimal st-Cuts

    • Alessio Conte, Roberto Grossi, Andrea Marino, Romeo Rizzi, Takeaki Uno, Luca Versari
    Pages 100-110

  11. Subexponential-Time and FPT Algorithms for Embedded Flat Clustered Planarity

    • Giordano Da Lozzo, David Eppstein, Michael T. Goodrich, Siddharth Gupta
    Pages 111-124

  12. Computing Small Pivot-Minors

    • Konrad K. Dabrowski, François Dross, Jisu Jeong, Mamadou Moustapha Kanté, O-joung Kwon, Sang-il Oum et al.
    Pages 125-138

  13. Saving Probe Bits by Cube Domination

    • Peter Damaschke
    Pages 139-151

  14. Graph Amalgamation Under Logical Constraints

    • Mateus de Oliveira Oliveira
    Pages 152-163

  15. \(\forall \exists \mathbb {R}\)-Completeness and Area-Universality

    • Michael Gene Dobbins, Linda Kleist, Tillmann Miltzow, Paweł Rzążewski
    Pages 164-175

  16. Optimal General Matchings

    • Szymon Dudycz, Katarzyna Paluch
    Pages 176-189

  17. Quasimonotone Graphs

    • Martin Dyer, Haiko Müller
    Pages 190-202

  18. Equiangular Polygon Contact Representations

    • Stefan Felsner, Hendrik Schrezenmaier, Raphael Steiner
    Pages 203-215

  19. Temporal Graph Classes: A View Through Temporal Separators

    • Till Fluschnik, Hendrik Molter, Rolf Niedermeier, Philipp Zschoche
    Pages 216-227

  20. Covering a Graph with Nontrivial Vertex-Disjoint Paths: Existence and Optimization

    • Renzo Gómez, Yoshiko Wakabayashi
    Pages 228-238
Back to top

Other volumes

  1. Graph-Theoretic Concepts in Computer Science

Keywords

About this book

This book constitutes the revised selected papers of the 44th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2018, held  in Cottbus, Germany, in June 2018.

The 30 full papers presented in this volume were carefully reviewed and selected from 66 submissions. They cover a wide range of areas, aiming at connecting theory and applications by demonstrating how graph-theoretic concepts can be applied in various areas of computer science. Another focus is on presenting recent results and on identifying and exploring promising directions of future research.

Editors and Affiliations

  • Universität Rostock, Rostock, Germany

    Andreas Brandstädt

  • Brandenburgische Technische Universität Cottbus-Senftenberg, Cottbus, Germany

    Ekkehard Köhler, Klaus Meer

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation