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

Parameterized complexity/multivariate complexity algorithmics is an exciting field of modern
algorithm design and analysis, with a broad range of theoretical and practical aspects that …

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 …

At the core of the seminal graph minor theory of Robertson and Seymour is a powerful
structural theorem capturing the structure of graphs excluding a fixed minor. This result is …

Bidimensionality theory appears to be a powerful framework in the development of meta-
algorithmic techniques. It was introduced by Demaine et al.[J. ACM 2005] as a tool to obtain …

We introduce a new approach to design parameterized algorithms on planar graphs which
builds on the seminal results of Robertson and Seymour on graph minors. Graph minors …

We study a general family of facility location problems defined on planar graphs and on the
2-dimensional plane. In these problems, a subset of k objects has to be selected, satisfying …

We give a review of a series of techniques and results on the design of subexponential
parameterized algorithms for graph problems. The design of such algorithms usually …

We prove that any H-minor-free graph, for a fixed graph H, of treewidth w has an Ω (w)× Ω
(w) grid graph as a minor. Thus grid minors suffice to certify that H-minorfree graphs have …