H. L. Alber, H. Bodlaender, T. Fernau, R. Kloks, and . Niedermeier, Fixed Parameter Algorithms for DOMINATING SET and Related Problems on Planar Graphs, Algorithmica, vol.33, issue.4, pp.461-493, 2002.
DOI : 10.1007/s00453-001-0116-5

M. R. Alber, R. Fellows, and . Niedermeier, Polynomial-time data reduction for dominating set, Journal of the ACM, vol.51, issue.3, pp.363-384, 2004.
DOI : 10.1145/990308.990309

R. Alber and . Niedermeier, Improved tree decomposition based algorithms for dominationlike problems, Theoretical Informatics, pp.221-233, 2002.

J. Arnborg, D. Lagergren, and . Seese, Easy problems for tree-decomposable graphs, Journal of Algorithms, vol.12, issue.2, pp.308-340, 1991.
DOI : 10.1016/0196-6774(91)90006-K

R. Betzler, J. Niedermeier, and . Uhlmann, Tree decompositions of graphs: Saving memory in dynamic programming, Graphs and Combinatorial Optimization, pp.220-229, 2006.
DOI : 10.1016/j.disopt.2006.05.008

T. Björklund, P. Husfeldt, M. Kaski, and . Koivisto, Fourier meets Möbius: fast subset convolution, STOC, pp.67-74, 2007.

F. Bodlaender, D. Fomin, E. Lokshtanov, S. Penninkx, D. Saurabh et al., (Meta) kernelization, 50th Annual IEEE Symposium on Foundations of Computer Science, 2009.
URL : https://hal.archives-ouvertes.fr/lirmm-00904532

L. Bodlaender, Dynamic programming on graphs with bounded treewidth, 15th International Colloquium on Automata, Languages and Programming (ICALP), pp.105-118, 1988.
DOI : 10.1007/3-540-19488-6_110

L. Bodlaender, P. G. Drange, M. S. Dregi, F. V. Fomin, D. Lokshtanov et al., An O(c k n) 5-approximation algorithm for treewidth, 54th Annual IEEE Symposium on Foundations of Computer Science, pp.499-508, 2013.

L. Bodlaender and E. Penninkx, A Linear Kernel for Planar Feedback Vertex Set, Proccedings of the 3rd International Workshop on Exact and Parameterized Computation, pp.160-171, 2008.
DOI : 10.1007/978-3-540-79723-4_16

L. Bodlaender, E. Penninkx, and R. B. Tan, A Linear Kernel for the k-Disjoint Cycle Problem on Planar Graphs, 19th International Symposium on Algorithms and Computation (ISAAC), pp.306-317, 2008.
DOI : 10.1007/978-3-540-92182-0_29

L. Bodlaender and J. A. Telle, Space-efficient construction variants of dynamic programming, Nordic J. Comput, vol.11, issue.4, pp.374-385, 2004.

D. Cai and . Juedes, On the existence of subexponential parameterized algorithms, Journal of Computer and System Sciences, vol.67, issue.4, pp.789-807, 2003.
DOI : 10.1016/S0022-0000(03)00074-6

J. Chekuri and . Chuzhoy, Polynomial bounds for the grid-minor theorem. CoRR, abs/1305, 2013.

J. Chekuri and . Chuzhoy, Degree-3 Treewidth Sparsifiers, Proceedings of the Twenty- Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, pp.242-255, 2015.
DOI : 10.1137/1.9781611973730.19

H. Chen, I. A. Fernau, G. Kanj, and . Xia, Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size, SIAM Journal on Computing, vol.37, issue.4, pp.1077-1106, 2007.
DOI : 10.1137/050646354

I. A. Chen, W. Kanj, and . Jia, Vertex Cover: Further Observations and Further Improvements, Journal of Algorithms, vol.41, issue.2, pp.280-301, 2001.
DOI : 10.1006/jagm.2001.1186

I. A. Chen, L. Kanj, E. Perkovi?, G. Sedgwick, and . Xia, Genus characterizes the complexity of certain graph problems: Some tight results, Journal of Computer and System Sciences, vol.73, issue.6, pp.892-907, 2007.
DOI : 10.1016/j.jcss.2006.11.001

. Chuzhoy, Excluded Grid Theorem, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC '15, pp.645-654, 2015.
DOI : 10.1145/2746539.2746551

. Courcelle, The monadic second-order logic of graphs. I. Recognizable sets of finite graphs, Information and Computation, vol.85, issue.1, pp.12-75, 1990.
DOI : 10.1016/0890-5401(90)90043-H

URL : https://hal.archives-ouvertes.fr/hal-00353765

. Courcelle, The expression of graph properties and graph transformations in monadic second-order logic. Handbook of Graph Grammars, pp.313-400, 1997.

F. V. Cygan, L. Fomin, D. Kowalik, D. Lokshtanov, M. Marx et al., Parameterized Algorithms, 2015.
DOI : 10.1007/978-3-319-21275-3

S. Cygan, J. Kratsch, and . Nederlof, Fast hamiltonicity checking via bases of perfect matchings, Proceedings of the 45th annual ACM symposium on Symposium on theory of computing, STOC '13, pp.301-310, 2013.
DOI : 10.1145/2488608.2488646

J. Cygan, M. Nederlof, M. Pilipczuk, J. M. Pilipczuk, J. O. Van-rooij et al., Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time, 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pp.150-159, 2011.
DOI : 10.1109/FOCS.2011.23

D. Demaine, Algorithmic graph minors and bidimensionality, Graph Theoretic Concepts in Computer Science -36th International Workshop, 2010.

D. Demaine, F. V. Fomin, M. Hajiaghayi, and D. M. Thilikos, -minor-free graphs, Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp.830-839, 2004.
DOI : 10.1145/1101821.1101823

URL : https://hal.archives-ouvertes.fr/lirmm-00904522

D. Demaine, F. V. Fomin, M. Hajiaghayi, and D. M. Thilikos, Bidimensional Parameters and Local Treewidth, SIAM Journal on Discrete Mathematics, vol.18, issue.3, pp.501-511, 2005.
DOI : 10.1137/S0895480103433410

D. M. Thilikos, E. D. Demaine, F. V. Fomin, M. Hajiaghayi, and D. M. Thilikos, Fixed-parameter algorithms for (k, r)-center in planar graphs and map graphs, ACM Trans. Algorithms, vol.1, issue.1, pp.33-47, 2005.

D. Demaine, F. V. Fomin, M. Hajiaghayi, and D. M. Thilikos, Bidimensional structures: Algorithms, combinatorics and logic (dagstuhl seminar 13121) Dagstuhl Reports, pp.51-74, 2013.

D. Demaine, F. V. Fomin, M. T. Hajiaghayi, and D. M. Thilikos, )-center in planar graphs and map graphs, ACM Transactions on Algorithms, vol.1, issue.1, pp.33-47, 2005.
DOI : 10.1145/1077464.1077468

D. Demaine and M. Hajiaghayi, Bidimensionality, map graphs, and grid minors. CoRR, abs/cs, 2005.

D. Demaine and M. Hajiaghayi, Bidimensionality, 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pp.590-601, 2005.
DOI : 10.1007/978-0-387-30162-4_47

URL : https://hal.archives-ouvertes.fr/lirmm-01483707

D. Demaine and M. Hajiaghayi, The Bidimensionality Theory and Its Algorithmic Applications, The Computer Journal, vol.51, issue.3, pp.292-302, 2008.
DOI : 10.1093/comjnl/bxm033

D. Demaine and M. Hajiaghayi, Linearity of grid minors in treewidth with applications through bidimensionality, Combinatorica, vol.14, issue.2, pp.19-36, 2008.
DOI : 10.1007/s00493-008-2140-4

D. Demaine, M. Hajiaghayi, and K. Kawarabayashi, Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner???s Contraction, Algorithmica, vol.9, issue.6, pp.142-180, 2009.
DOI : 10.1007/s00453-007-9138-y

D. Demaine, M. Hajiaghayi, and D. M. Thilikos, Exponential Speedup of Fixed-Parameter Algorithms for Classes of Graphs Excluding Single-Crossing Graphs as Minors, Algorithmica, vol.41, issue.4, pp.245-267, 2005.
DOI : 10.1007/s00453-004-1125-y

D. Demaine, M. Hajiaghayi, and D. M. Thilikos, The Bidimensional Theory of Bounded-Genus Graphs, SIAM Journal on Discrete Mathematics, vol.20, issue.2, pp.357-371, 2006.
DOI : 10.1137/040616929

D. Demaine and M. T. Hajiaghayi, Fast Algorithms for Hard Graph Problems: Bidimensionality, Minors, and Local Treewidth, Graph Drawing, 12th International Symposium, pp.517-533, 2004.
DOI : 10.1007/978-3-540-31843-9_57

. Dorn, Dynamic Programming and Fast Matrix Multiplication, 14th Annual European Symposium on Algorithms, pp.280-291, 2006.
DOI : 10.1007/11841036_27

F. V. Dorn, D. Fomin, V. Lokshtanov, S. Raman, and . Saurabh, Beyond bidimensionality: Parameterized subexponential algorithms on directed graphs, Information and Computation, vol.233, issue.0, pp.60-70, 2013.
DOI : 10.1016/j.ic.2013.11.006

URL : https://hal.archives-ouvertes.fr/inria-00455210

F. V. Dorn, D. M. Fomin, and . Thilikos, Fast Subexponential Algorithm for Non-local Problems on Graphs of Bounded Genus, 10th Scandinavian Workshop on Algorithm Theory, pp.172-183, 2006.
DOI : 10.1007/11785293_18

F. V. Dorn, D. M. Fomin, and . Thilikos, Catalan structures and dynamic programming in H-minor-free graphs, ACM-SIAM Symposium on Discrete Algorithms, pp.631-640, 2008.
DOI : 10.1016/j.jcss.2012.02.004

URL : https://hal.archives-ouvertes.fr/lirmm-00904498

F. V. Dorn, D. M. Fomin, and . Thilikos, Subexponential parameterized algorithms, Computer Science Review, vol.2, issue.1, pp.29-39, 2008.
DOI : 10.1016/j.cosrev.2008.02.004

URL : https://hal.archives-ouvertes.fr/inria-00455210

E. Dorn, H. L. Penninkx, F. V. Bodlaender, and . Fomin, Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Decompositions, Algorithmica, vol.15, issue.2, pp.790-810, 2010.
DOI : 10.1007/s00453-009-9296-1

G. Downey and M. R. Fellows, Parameterized complexity. Monographs in Computer Science, 1999.

F. Dragan, F. V. Fomin, and P. A. Golovach, Spanners in sparse graphs, 35th International Colloquium on Automata, Languages and Programming, pp.597-608, 2008.

P. Bidimensionality, H. Algorithms, and . Fernau, Graph separator algorithms: a refined analysis, Graph-theoretic Concepts in Computer Science, pp.186-197, 2002.

D. Fernau and . Juedes, A Geometric Approach to Parameterized Algorithms for Domination Problems on Planar Graphs, 29th International Symposium on Mathematical Foundations of Computer, pp.488-499, 2004.
DOI : 10.1007/978-3-540-28629-5_37

M. Flum and . Grohe, Parameterized Complexity theory. Texts in Theoretical Computer Science. An EATCS Series, 2006.

V. Fomin, S. S. Lokshtanov, and D. M. Thilikos, -minor-free graphs, 23st ACM?SIAM Symposium on Discrete Algorithms, 2012.
DOI : 10.1137/1.9781611973099.7

URL : https://hal.archives-ouvertes.fr/inria-00358112

V. Fomin, P. Golovach, and D. M. Thilikos, Contraction Bidimensionality: The Accurate Picture, 17th Annual European Symposium on Algorithms, pp.706-717, 2009.
DOI : 10.1007/978-3-642-04128-0_63

V. Fomin, P. A. Golovach, and D. M. Thilikos, Contraction obstructions for treewidth, Journal of Combinatorial Theory, Series B, vol.101, issue.5, pp.302-314, 2011.
DOI : 10.1016/j.jctb.2011.02.008

V. Fomin, D. Lokshtanov, V. Raman, and S. Saurabh, Subexponential algorithms for partial cover problems, Information Processing Letters, vol.111, issue.16, pp.814-818, 2011.
DOI : 10.1016/j.ipl.2011.05.016

V. Fomin, D. Lokshtanov, and S. Saurabh, Bidimensionality and Geometric Graphs, Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, pp.1563-1575, 2012.
DOI : 10.1137/1.9781611973099.124

V. Fomin, D. Lokshtanov, and S. Saurabh, Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms, Proceedings of the Twenty- Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '14, pp.142-151, 2014.
DOI : 10.1137/1.9781611973402.10

V. Fomin, D. Lokshtanov, S. Saurabh, and D. M. Thilikos, Bidimensionality and Kernels, 21st Annual ACM-SIAM Symposium on Discrete Algorithms, pp.503-510, 2010.
DOI : 10.1137/1.9781611973075.43

V. Fomin, D. Lokshtanov, S. Saurabh, and D. M. Thilikos, Linear kernels for (connected) dominating set on graphs with excluded topological subgraphs, 30th International Symposium on Theoretical Aspects of Computer Science of Leibniz International Proceedings in Informatics (LIPIcs) Schloss Dagstuhl?Leibniz-Zentrum fuer Informatik, pp.92-103, 2013.
URL : https://hal.archives-ouvertes.fr/lirmm-00804758

V. Fomin and D. M. Thilikos, Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up, SIAM Journal on Computing, vol.36, issue.2, pp.281-309, 2006.
DOI : 10.1137/S0097539702419649

C. Garnero, I. Paul, D. M. Sau, and . Thilikos, Explicit Linear Kernels via Dynamic Programming, 31st International Symposium on Theoretical Aspects of Computer Science STACS 2014, pp.312-324, 2014.
DOI : 10.1137/140968975

URL : https://hal.archives-ouvertes.fr/hal-01084007

I. Garnero, D. M. Sau, and . Thilikos, A linear kernel for planar red???blue dominating set, Proceedings of the 12th Cologne Twente Workshop on Graphs and Combinatorial Optimization (CTW), pp.117-120, 2013.
DOI : 10.1016/j.dam.2016.09.045

URL : https://hal.archives-ouvertes.fr/lirmm-01481785

C. Giannopoulou and D. M. Thilikos, Optimizing the Graph Minors Weak Structure Theorem, SIAM Journal on Discrete Mathematics, vol.27, issue.3, pp.1209-1227, 2013.
DOI : 10.1137/110857027

URL : https://hal.archives-ouvertes.fr/lirmm-00904527

D. M. Thilikos, P. A. Golovach, M. Kami?ski, D. Paulusma, and D. M. Thilikos, Induced packing of odd cycles in a planar graph, 20th International Symposium on Algorithms and Computation, pp.514-523, 2009.

A. Grigoriev, D. Koutsonas, and . Thilikos, Bidimensionality of Geometric Intersection Graphs, SOFSEM 2014, pp.293-305, 2014.
DOI : 10.1007/978-3-319-04298-5_26

URL : https://hal.archives-ouvertes.fr/lirmm-00904537

R. Guo, S. Niedermeier, and . Wernicke, Fixed-parameter tractability results for fulldegree spanning tree and its dual, Second International Workshop on Parameterized and Exact Computation (IWPEC), pp.203-214, 2006.

M. J. Kanj, M. Pelsmajer, G. Schaefer, and . Xia, On the induced matching problem, Journal of Computer and System Sciences, vol.77, issue.6, pp.1058-1070, 2011.
DOI : 10.1016/j.jcss.2010.09.001

URL : https://hal.archives-ouvertes.fr/hal-00231081

L. Kanj and . Perkovi?, Improved Parameterized Algorithms for Planar Dominating Set, 27th International Symposium Mathematical Foundations of Computer Science, pp.399-410, 2002.
DOI : 10.1007/3-540-45687-2_33

C. M. Kloks, J. Lee, and . Liu, New Algorithms for k-Face Cover, k-Feedback Vertex Set, and k-Disjoint Cycles on Plane and Planar Graphs, 28th International Workshop on Graph Theoretic Concepts in Computer Science, pp.282-295, 2002.
DOI : 10.1007/3-540-36379-3_25

D. M. Koutsonas and . Thilikos, Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms, Algorithmica, vol.14, issue.2, pp.987-1003, 2011.
DOI : 10.1007/s00453-010-9390-4

. Kratsch, Recent developments in kernelization: A survey, Bulletin of the EATCS, vol.113, 2014.

N. Lokshtanov, S. Misra, and . Saurabh, Kernelization ??? Preprocessing with a Guarantee, The Multivariate Algorithmic Revolution and Beyond -Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday, pp.129-161, 2012.
DOI : 10.1016/0304-3975(76)90061-X

M. Lokshtanov, S. Mnich, and . Saurabh, Linear kernel for planar connected dominating set, 6th Annual Conference on Theory and Applications of Models of Computation, pp.281-290, 2009.

S. Moser and . Sikdar, The Parameterized Complexity of the Induced Matching Problem in Planar Graphs, Proceedings First Annual International WorkshopFrontiers in Algorithmics (FAW), pp.325-336, 2007.
DOI : 10.1007/978-3-540-73814-5_32

. Niedermeier, Invitation to fixed-parameter algorithms, volume 31 of Oxford Lecture Series in Mathematics and its Applications, 2006.

. Pilipczuk, Problems Parameterized by Treewidth Tractable in Single Exponential Time: A??Logical Approach, Mathematical Foundations of Computer Science 2011, pp.520-531, 2011.
DOI : 10.1007/978-3-642-22993-0_47

M. Pilipczuk, P. Pilipczuk, E. J. Sankowski, and . Van-leeuwen, Subexponential-time parameterized algorithm for steiner tree on planar graphs, 30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013, pp.353-364, 2013.

M. Pilipczuk, P. Pilipczuk, E. J. Sankowski, and . Van-leeuwen, Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs, 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp.276-285, 2014.
DOI : 10.1109/FOCS.2014.37

P. D. Robertson and . Seymour, Graph minors. V. Excluding a planar graph, Journal of Combinatorial Theory, Series B, vol.41, issue.1, pp.92-114, 1986.
DOI : 10.1016/0095-8956(86)90030-4

P. D. Robertson, R. Seymour, and . Thomas, Quickly Excluding a Planar Graph, Journal of Combinatorial Theory, Series B, vol.62, issue.2, pp.323-348, 1994.
DOI : 10.1006/jctb.1994.1073

P. Bidimensionality, 8. J. Algorithms, I. Rué, D. M. Sau, and . Thilikos, Dynamic programming for graphs on surfaces, Automata, Languages and Programming, 37th International Colloquium, pp.372-383, 2010.

I. Rué, D. M. Sau, and . Thilikos, Asymptotic enumeration of non-crossing partitions on surfaces, Discrete Mathematics, vol.313, issue.5, pp.635-649, 2013.
DOI : 10.1016/j.disc.2012.12.011

M. Thilikos, Fast Sub-exponential Algorithms and Compactness in Planar Graphs, 19th Annual European Symposium on Algorithms, pp.358-369, 2011.
DOI : 10.1007/978-3-642-23719-5_31

. Thomassé, A 4·k 2 kernel for feedback vertex set, ACM Trans. Algorithms, vol.632, issue.2, pp.1-32, 2010.

M. M. Van-rooij, H. L. Bodlaender, and P. Rossmanith, Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution, ESA, pp.566-577, 2009.
DOI : 10.1007/978-3-642-04128-0_51

. Wollan, The structure of graphs not admitting a fixed immersion, Journal of Combinatorial Theory, Series B, vol.110, pp.47-66, 2015.
DOI : 10.1016/j.jctb.2014.07.003