Graph Decompositions and Algorithms (Invited Talk)
Fedor V. Fomin · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2016
We overview the recent progress in solving intractable optimization problems on planar graphs as well as other classes of sparse graphs. In particular, we discuss how tools from Graph Minors theory can be used to obtain: * subexponential parameterized algorithms * approximation algorithms, and * preprocessing and kernelization algorithms on these classes of graphs.