Parameterized complexity: exponential speed-up for planar graph problems

We discuss general techniques, centered around the “Layerwise Separation Property” (LSP) of a planar graph problem, that allow to develop algorithms with running time <f>c√ of k&z.sfnc;G&z.sfnc;</f>, given an instance <f>G</f> of a problem on planar graphs with parameter <f>k</f>. Problems having LSP include planar vertex cover, planar independent set, and planar dominating set. Extensions of our speed-up technique to basically all fixed-parameter tractable planar graph problems are also exhibited. Moreover, we relate, e.g., the domination number or the vertex cover number, with the treewidth of a plane graph. [Copyright &y& Elsevier]