This book constitutes revised selected papers from the 41st International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2015, held in Garching, Germany, in June 2015.
The 32 papers presented in this volume were carefully reviewed and selected from 79 submissions. They were organized in topical sections named: invited talks; computational complexity; design and analysis; computational geometry; structural graph theory; graph drawing; and fixed parameter tractability.
Invited Talks.- Parameterized Algorithmics for Graph Modification
Problems: On Interactions with Heuristics.- Open Problems on Graph Coloring
for Special Graph Classes.- On the Complexity of Approximation and Online
Scheduling Problems with Applications to Optical Networks.- Computational
Complexity.- The Stable Fixtures Problem with Payments.- Complexity of Secure
Sets.- Efficient Domination for Some Subclasses of P6-free Graphs in
Polynomial Time.- On the Tree Search Problem with Non-uniform Costs.- An
O(n2) Time Algorithm for the Minimal Permutation Completion Problem.- On the
Number of Minimal Separators in Graphs.- Efficient Farthest-Point Queries in
Two-terminal Series-parallel Networks.- A Polynomial Delay Algorithm for
Enumerating Minimal Dominating Sets in Chordal Graphs.- Finding Paths in
Grids with Forbidden Transitions.- The Maximum Time of 2-neighbour Bootstrap
Percolation in Grid Graphs and Parametrized Results.- Design and Analysis.-
Minimum Eccentricity Shortest Paths in Some Structured Graph Classes.-
Approximating Source Location and Star Survivable Network Problems.- On the
Complexity of Computing the k-restricted Edge-connectivity of a Graph.-
Computational Geometry.- Weak Unit Disk and Interval Representation of
Graphs.- Simultaneous Visibility Representations of Plane st-graphs Using
L-shapes.- An Abstract Approach to Polychromatic Coloring: Shallow Hitting
Sets in ABA-free Hypergraphs and Pseudohalfplanes.- Unsplittable Coverings in
the Plane.- Structural Graph Theory.- Induced Minor Free Graphs: Isomorphism
and Clique-width.- On the Complexity of Probe and Sandwich Problems for
Generalized Threshold Graphs.- Colouring and Covering Nowhere Dense Graphs.-
Parity Linkage and the Erdös-Pósa Property of Odd Cycles Through Prescribed
Vertices in Highly Connected Graphs.- Well-quasi-ordering Does Not Imply
Bounded Clique-width.- A Slice Theoretic Approach for Embedding Problems on
Digraphs.- Decomposition Theorems for Square-free 2-matchings in Bipartite
Graphs.- Graph Drawing.- Saturated Simple and 2-simple Topological Graphs
with Few Edges.- Testing Full Outer-2-planarity in Linear Time.- Fixed
Parameter Tractability.- Triangulating Planar Graphs While Keeping the
Pathwidth Small.- Polynomial Kernelization for Removing Induced Claws and
Diamonds.- Algorithms and Complexity for Metric Dimension and
Location-domination on Interval and Permutation Graphs.- On Structural
Parameterizations of Hitting Set: Hitting Paths in Graphs Using 2-SAT.-
Recognizing k-equistable Graphs in FPT Time.- Beyond Classes of Graphs with
\Few" Minimal Separators: FPT.- Results Through Potential Maximal Cliques.
