Skip to main content
SpringerLink
Log in

Graph-Theoretic Concepts in Computer Science

46th International Workshop, WG 2020, Leeds, UK, June 24–26, 2020, Revised Selected Papers

  • Conference proceedings
  • © 2020

Overview

Editors:
  1. Isolde Adler

    1. University of Leeds, Leeds, UK

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Haiko Müller

    1. University of Leeds, Leeds, UK

    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 12301)

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

Included in the following conference series:

Conference proceedings info: WG 2020.

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 (32 papers)

  1. Front Matter

    Pages i-xv
    Download chapter PDF

  2. Combinatorial Bounds for Conflict-Free Coloring on Open Neighborhoods

    • Sriram Bhyravarapu, Subrahmanyam Kalyanasundaram
    Pages 1-13

  3. Guarding Quadrangulations and Stacked Triangulations with Edges

    • Paul Jungeblut, Torsten Ueckerdt
    Pages 14-26

  4. Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space

    • Jesper Nederlof, Michał Pilipczuk, Céline M. F. Swennenhuis, Karol Węgrzycki
    Pages 27-39

  5. Parameterized Inapproximability of Independent Set in H-Free Graphs

    • Pavel Dvořák, Andreas Emil Feldmann, Ashutosh Rai, Paweł Rzążewski
    Pages 40-53

  6. Clique-Width of Point Configurations

    • Onur Çağırıcı, Petr Hliněný, Filip Pokrývka, Abhisekh Sankaran
    Pages 54-66

  7. On the Complexity of Finding Large Odd Induced Subgraphs and Odd Colorings

    • Rémy Belmonte, Ignasi Sau
    Pages 67-79

  8. Knot Diagrams of Treewidth Two

    • Hans L. Bodlaender, Benjamin Burton, Fedor V. Fomin, Alexander Grigoriev
    Pages 80-91

  9. Treewidth Versus Clique Number in Graph Classes with a Forbidden Structure

    • Clément Dallard, Martin Milanič, Kenny Štorgel
    Pages 92-105

  10. Graph Isomorphism Restricted by Lists

    • Pavel Klavík, Dušan Knop, Peter Zeman
    Pages 106-118

  11. Clique-Width: Harnessing the Power of Atoms

    • Konrad K. Dabrowski, Tomáš Masařík, Jana Novotná, Daniël Paulusma, Paweł Rzążewski
    Pages 119-133

  12. Edge Elimination and Weighted Graph Classes

    • Jesse Beisegel, Nina Chiarelli, Ekkehard Köhler, Matjaž Krnc, Martin Milanič, Nevena Pivač et al.
    Pages 134-147

  13. Well-Partitioned Chordal Graphs: Obstruction Set and Disjoint Paths

    • Jungho Ahn, Lars Jaffke, O-joung Kwon, Paloma T. Lima
    Pages 148-160

  14. Plattenbauten: Touching Rectangles in Space

    • Stefan Felsner, Kolja Knauer, Torsten Ueckerdt
    Pages 161-173

  15. Universal Geometric Graphs

    • Fabrizio Frati, Michael Hoffmann, Csaba D. Tóth
    Pages 174-186

  16. Computing Subset Transversals in H-Free Graphs

    • Nick Brettell, Matthew Johnson, Giacomo Paesani, Daniël Paulusma
    Pages 187-199

  17. Feedback Edge Sets in Temporal Graphs

    • Roman Haag, Hendrik Molter, Rolf Niedermeier, Malte Renken
    Pages 200-212

  18. On Flips in Planar Matchings

    • Marcel Milich, Torsten Mütze, Martin Pergel
    Pages 213-225

  19. Degree Distribution for Duplication-Divergence Graphs: Large Deviations

    • Alan Frieze, Krzysztof Turowski, Wojciech Szpankowski
    Pages 226-237

  20. On Finding Balanced Bicliques via Matchings

    • Parinya Chalermsook, Wanchote Po Jiamjitrak, Ly Orgo
    Pages 238-247
Back to top

Other volumes

  1. Graph-Theoretic Concepts in Computer Science

Keywords

About this book

This book constitutes the revised papers of the 46th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2020, held in Leeds, UK, in June 2020. The workshop was held virtually due to the COVID-19 pandemic.

The 32 full papers presented in this volume were carefully reviewed and selected from 94 submissions. They cover a wide range of areas, aiming to present emerging research results and to identify and explore directions of future research of concepts on graph theory and how they can be applied to various areas in computer science.

Editors and Affiliations

  • University of Leeds, Leeds, UK

    Isolde Adler, Haiko Müller

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation