Includes author index.

Online resource; title from PDF title page (SpringerLink, viewed November 9, 2017).

This book constitutes the revised selected papers of the 43rd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2017, held in Eindhoven, The Netherlands, in June 2017. The 31 full papers presented in this volume were carefully reviewed and selected from 71 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.

Intro; Preface; Organization; Contents; Counting Graphs and Null Models of Complex Networks: Configuration Model and Extensions; 1 Complex Networks and Random Graphs: A Motivation; 2 Random Graphs and Real-World Networks; 3 Random Graph Models as Null Models; 3.1 Null Model 1: Uniform Random Graph; 3.2 Null Model 2: Erdős-Rényi Random Graph with Fixed Number of Edges; 3.3 Null Model 3: Fixing All Degrees and the Configuration Model; 3.4 Small-World Properties of the Configuration Model; 4 Extensions: Other Models; References; On Bubble Generators in Directed Graphs; 1 Introduction.

2 Preliminaries3 The Bubble Generator; 4 A Polynomial-Time Algorithm for Decomposing a Bubble; 5 Conclusions and Open Problems; References; Critical Node Cut Parameterized by Treewidth and Solution Size is W[1]-Hard; 1 Introduction; 2 Preliminaries; 3 W[1]-HardNess of SumCSP; 4 W[1]-HardNess of CNC; References; Hierarchical Partial Planarity; 1 Introduction; 2 Preliminaries; 3 Relationships to Other Planarity Problems; 4 Biconnected Facial-Constrained Core Planarity; 4.1 High-Level Description of the Algorithm; 4.2 Detailed Description of the Algorithm; 5 Open Problems; References.

On the Relationship Between k-Planar and k-Quasi-Planar Graphs1 Introduction; 2 Preliminaries; 3 Edge Rerouting Operations and Proof Strategy; 4 Removing Tangled (k+1)-Crossings; 5 Removing Untangled (k+1)-Crossings; 5.1 Obtaining (k+1)-Quasi-Planarity; 5.2 Obtaining Simplicity; 6 Conclusions and Open Problems; References; Extension Complexity of Stable Set Polytopes of Bipartite Graphs; 1 Introduction; 2 Rectangle Covers and Fooling Sets; 3 An Improved Upper Bound; 4 An Improved Lower Bound; 5 A Small Rectangle Cover of the Special Entries; References.

On the Number of Labeled Graphs of Bounded Treewidth1 Introduction; 2 The Construction; 2.1 Notation and Definitions; 2.2 Description of the Construction; 2.3 Bounding the Treewidth; 3 Proof of the Main Result; 3.1 Number of Constructible Triples (, F, N); 3.2 Bounding the Number of Duplicates; 3.3 Choosing the Parameter s; 4 Concluding Remarks and Further Research; References; Uniquely Restricted Matchings and Edge Colorings; 1 Introduction; 2 Approximation Algorithms for Bipartite Graphs; 3 Upper Bounds on ur'(G); 4 Concluding Remarks; References.

Defective Coloring on Classes of Perfect Graphs1 Introduction; 2 Preliminaries and Definitions; 3 NP-Hardness on Cographs; 4 Polynomial Time Algorithm on Trivially Perfect Graphs; 5 Algorithms on Cographs; 5.1 Algorithm for Small Deficiency; 5.2 Algorithm for Few Colors; 5.3 Sub-Exponential Time Algorithm; 6 Split and Chordal Graphs; 6.1 Hardness for Bounded Deficiency; 6.2 Hardness for Bounded Number of Colors; 6.3 A Dynamic Programming Algorithm; 7 Conclusions; References; Token Sliding on Chordal Graphs; 1 Introduction; 2 Hardness Results; 2.1 Split Graphs; 2.2 Bipartite Graphs.