Bidimensionality theory characterizes a broad range of graph problems (bidimensional) that admit efficient approximate, fixed-parameter or kernel solutions in a broad range of graphs. These graph classes include planar graphs, map graphs, bounded-genus graphs and graphs excluding any fixed minor. In particular, bidimensionality theory builds on the graph minor theory of Robertson and Seymour by extending the mathematical results and building new algorithmic tools. The theory was introduced in the work of Demaine, Fomin, Hajiaghayi, and Thilikos, for which the authors received the Nerode Prize in 2015. Definition A parameterized problem is a subset of for some finite alphabet . An instance of a parameterized problem consists of (x,k), where k is called the parameter. A parameterized problem is minor-bidimensional if For any pair of graphs , such that is a minor of and integer , yields that . In other words, contracting or deleting an edge in a graph cannot increase the parameter; and there is such that for every -grid , for every . In other words, the value of the solution on should be at least . Examples of minor-bidimensional problems are the parameterized versions of vertex cover, feedback vertex set, minimum maximal matching, and longest path. Let be the graph obtained from the -grid by triangulating internal faces such that all internal vertices become of degree 6, and then one corner of degree two joined by edges with all vertices of the external face. A parameterized problem is contraction-bidimensional if For any pair of graphs , such that is a contraction of and integer , yields that . In other words, contracting an edge in a graph cannot increase the parameter; and there is such that for every . Examples of contraction-bidimensional problems are dominating set, connected dominating set, max-leaf spanning tree, and edge dominating set. Excluded grid theorems All algorithmic applications of bidimensionality are based on the following combinatorial property: either the treewidth of a graph is small, or the graph contains a large grid as a minor or contraction. More precisely, There is a function f such that every graph G excluding a fixed h-vertex graph as a minor and of treewidth at least f(h)r contains (r x r)-grid as a minor. There is a function g such that every graph G excluding a fixed h-vertex apex graph as a minor and of treewidth at least g(h) r can be edge-contracted to . Halin's