This paper surveys the theory of bidimensionality. This theory characterizes a broad range of
graph problems ('bidimensional') that admit efficient approximate or fixed-parameter …

For the vast majority of local problems on graphs of small tree width (where by local we
mean that a solution can be verified by checking separately the neighbourhood of each …

It is well known that many local graph problems, like Vertex Cover and Dominating Set, can
be solved in time 2 O (tw)| V| O (1) for graphs G=(V, E) with a given tree decomposition of …

We show that planar graphs have bounded queue-number, thus proving a conjecture of
Heath et al.[66] from 1992. The key to the proof is a new structural tool called layered …

We introduce a new framework for designing fixed-parameter algorithms with
subexponential running time---2 O (√ k) n O (1). Our results apply to a broad family of graph …

Approximation algorithms and parameterized complexity are usually considered to be two
separate ways of dealing with hard algorithmic problems. In this paper, our aim is to …

Descriptive complexity theory establishes a connection between the computational
complexity of algorithmic problems (the computational resources required to solve the …

In the core of the seminal Graph Minor Theory of Robertson and Seymour lies a powerful
theorem capturing the``rough''structure of graphs excluding a fixed minor. This result was …

Parameterization and approximation are two popular ways of co** with NP-hard
problems. More recently, the two have also been combined to derive many interesting …

We consider various well-known, equivalent complexity measures for graphs such as
elimination orderings, k-trees and cops and robber games and study their natural …