. Finally, Z ) has at least k + 1 vertices, then |N G k?2 (Z )| ? (k + 1)(k ? 3, pp.2-3

I. Adler, S. G. Kolliopoulos, P. K. Krause, D. Lokshtanov, S. Saurabh et al., Tight Bounds for Linkages in Planar Graphs, Automata, Languages and Programming -38th International Colloquium, ICALP 2011, pp.110-121, 2011.
DOI : 10.1016/0166-218X(93)E0177-Z

R. E. Aldred, S. Bau, D. A. Holton, and B. D. Mckay, Cycles Through 23 Vertices in 3-Connected Cubic Planar Graphs, Graphs and Combinatorics, vol.15, issue.4, pp.373-376, 1999.
DOI : 10.1007/s003730050046

H. L. Bodlaender, A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth, SIAM Journal on Computing, vol.25, issue.6, pp.1305-1317, 1996.
DOI : 10.1137/S0097539793251219

H. L. Bodlaender, F. V. Fomin, D. Lokshtanov, E. Penninkx, S. Saurabh et al., (meta) kernelization, Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pp.629-638, 2009.
DOI : 10.1109/focs.2009.46
URL : https://hal.archives-ouvertes.fr/lirmm-01483628

H. L. Bodlaender, B. M. Jansen, and S. Kratsch, Kernelization Lower Bounds by Cross-Composition, SIAM Journal on Discrete Mathematics, vol.28, issue.1, pp.277-305, 2014.
DOI : 10.1137/120880240
URL : http://arxiv.org/pdf/1206.5941.pdf

B. 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

B. Courcelle and J. Engelfriet, Graph Structure and Monadic Second-Order Logic -A Language-Theoretic Approach, Encyclopedia of mathematics and its applications, 2012.

E. 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

R. Diestel, Graph theory, Graduate Texts in Mathematics, vol.173, 2010.

G. A. Dirac, In abstrakten Graphen vorhandene vollst??ndige 4-Graphen und ihre Unterteilungen, Mathematische Nachrichten, vol.2, issue.1-2, pp.61-85, 1960.
DOI : 10.1016/S1385-7258(54)50043-0

R. G. Downey and M. R. Fellows, Parameterized complexity, 1999.
DOI : 10.1007/978-1-4612-0515-9

R. Downey and M. Fellows, Fixed-parameter tractability and completeness. III. Some structural aspects of the W hierarchy, Complexity theory, pp.191-225, 1993.
DOI : 10.1137/s0097539792228228
URL : http://homepages.ecs.vuw.ac.nz/~downey/publications/1.pdf

R. G. Downey and M. R. Fellows, Fixed-parameter tractability and completeness, 21st Manitoba Conference on Numerical Mathematics and Computing, pp.161-178, 1991.
DOI : 10.1137/s0097539792228228
URL : http://homepages.ecs.vuw.ac.nz/~downey/publications/1.pdf

R. G. Downey and M. R. Fellows, Fixed-Parameter Tractability and Completeness I: Basic Results, SIAM Journal on Computing, vol.24, issue.4, pp.873-921, 1995.
DOI : 10.1137/S0097539792228228
URL : http://homepages.ecs.vuw.ac.nz/~downey/publications/1.pdf

R. G. Downey and M. R. Fellows, Fixed-parameter tractability and completeness II: On completeness for W[1], Theoretical Computer Science, vol.141, issue.1-2, pp.109-131, 1995.
DOI : 10.1016/0304-3975(94)00097-3

R. G. Downey and M. R. Fellows, Fundamentals of Parameterized Complexity, Texts in Computer Science, 2013.
DOI : 10.1007/978-1-4471-5559-1

P. Erd?-os, Remarks on a paper of Pósa, Magyar Tud. Akad. Mat. Kutató Int. Közl, vol.7, pp.227-229, 1962.

E. Flandrin, H. Li, A. Marczyk, and M. Wo´zniakwo´zniak, A generalization of Dirac's theorem on cycles through k vertices in k-connected graphs, Discrete Mathematics, vol.307, issue.7-8, pp.878-884, 2007.
DOI : 10.1016/j.disc.2005.11.052

F. 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
URL : https://doi.org/10.1016/j.jctb.2011.02.008

M. R. Garey, D. S. Johnson, and R. E. Tarjan, The Planar Hamiltonian Circuit Problem is NP-Complete, SIAM Journal on Computing, vol.5, issue.4, pp.704-714, 1976.
DOI : 10.1137/0205049

J. F. Geelen, R. B. Richter, and G. Salazar, Embedding grids in surfaces, European Journal of Combinatorics, vol.25, issue.6, pp.785-792, 2004.
DOI : 10.1016/j.ejc.2003.07.007

M. Grötschel, Hypohamiltonian facets of the symmetric travelling salesman polytope, Zeitschrift für Angewandte Mathematik und Mechanik, pp.469-471, 1977.

Q. P. Gu and H. Tamaki, Improved bounds on the planar branchwidth with respect to the largest grid minor size, Algorithms and Computation -21st International Symposium, pp.85-96, 2010.

K. I. Kawarabayashi and P. Wollan, A shorter proof of the graph minor algorithm, Proceedings of the 42nd ACM symposium on Theory of computing, STOC '10, 2010.
DOI : 10.1145/1806689.1806784

R. Niedermeier, Invitation to fixed-parameter algorithms, 2002.
DOI : 10.1093/acprof:oso/9780198566076.001.0001

L. Perkovic and B. A. Reed, AN IMPROVED ALGORITHM FOR FINDING TREE DECOMPOSITIONS OF SMALL WIDTH, International Journal of Foundations of Computer Science, vol.11, issue.03, pp.365-371, 2000.
DOI : 10.1016/0095-8956(88)90052-4

M. Plummer and E. Gy?-ori, A nine vertex theorem for 3-connected claw- free graphs, Studia Scientiarum Mathematicarum Hungarica, vol.38, issue.1-4, pp.233-244, 2001.
DOI : 10.1556/SScMath.38.2001.1-4.16

N. Robertson and P. Seymour, Graph Minors. XXII. Irrelevant vertices in linkage problems, Journal of Combinatorial Theory, Series B, vol.102, issue.2, pp.530-563, 2012.
DOI : 10.1016/j.jctb.2007.12.007
URL : https://doi.org/10.1006/jctb.1996.0059

N. Robertson and P. D. Seymour, Graph minors. X. Obstructions to tree-decomposition, Journal of Combinatorial Theory, Series B, vol.52, issue.2, pp.153-190, 1991.
DOI : 10.1016/0095-8956(91)90061-N
URL : https://doi.org/10.1006/jctb.1996.0059

N. Robertson and P. D. Seymour, Graph Minors .XIII. The Disjoint Paths Problem, Journal of Combinatorial Theory, Series B, vol.63, issue.1, pp.65-110, 1995.
DOI : 10.1006/jctb.1995.1006
URL : https://doi.org/10.1006/jctb.1996.0059

N. Robertson and P. D. Seymour, Graph Minors .XIII. The Disjoint Paths Problem, Journal of Combinatorial Theory, Series B, vol.63, issue.1, pp.65-110, 1995.
DOI : 10.1006/jctb.1995.1006
URL : https://doi.org/10.1006/jctb.1996.0059

N. Robertson and P. D. Seymour, Graph minors. XXI. Graphs with unique linkages, Journal of Combinatorial Theory, Series B, vol.99, issue.3, pp.583-616, 2009.
DOI : 10.1016/j.jctb.2008.08.003
URL : https://doi.org/10.1006/jctb.1996.0059

M. Watkins and D. Mesner, Cycles and connectivity in graphs, Journal canadien de math??matiques, vol.19, issue.0, pp.1319-1328, 1967.
DOI : 10.4153/CJM-1967-121-2