Graph Separators: A Parameterized View

Graph separation is a well-known tool to make (hard) graph problems accessible for a divide and conquer approach. We show how to use graph separator theorems in order to develop fixed parameter algorithms for many well-known NP-hard (planar) graph problems. We coin the key notion of glueable select&verify graph problems and derive from that a prospective way to easily check whether a planar graph problem will allow for a fixed parameter divide and conquer algorithm of running time c$$ ^{\sqrt k } $$ · nO(1) for a constant c.