H. 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, Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, pp.499-508, 2013.
DOI : 10.1109/focs.2013.60
URL : http://arxiv.org/abs/1304.6321

B. Bollobás, Extremal Graph Theory, 2004.
DOI : 10.1201/b16132-57

J. A. Bondy and U. S. Murty, Graph theory, Graduate Texts in Mathematics, vol.244, 2008.
DOI : 10.1007/978-1-84628-970-5

O. V. Borodin, Criterion of chromaticity of a degree prescription, IV All-Union Conf. on Theoretical Cybernetics (Novosibirsk), pp.127-128, 1977.

R. H. Chitnis, M. Hajiaghayi, and D. Marx, Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions), Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp.1782-1801, 2014.
DOI : 10.1137/1.9781611973402.129

E. 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
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.101.5930

I. Dinur, O. Regev, and C. Smyth, The Hardness of 3-Uniform Hypergraph Coloring, Combinatorica, vol.25, issue.5, pp.519-535, 2005.
DOI : 10.1007/s00493-005-0032-4

P. Erd?-os, A. L. Rubin, and H. Taylor, Choosability in graphs, Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing Congress. Numer., XXVI, pp.125-157, 1979.

M. R. Garey, D. S. Johnson, and L. Stockmeyer, Some simplified NP-complete graph problems, Theoretical Computer Science, vol.1, issue.3, pp.237-267, 1976.
DOI : 10.1016/0304-3975(76)90059-1
URL : http://doi.org/10.1016/0304-3975(76)90059-1

R. Impagliazzo, R. Paturi, and F. Zane, Which Problems Have Strongly Exponential Complexity?, Journal of Computer and System Sciences, vol.63, issue.4, pp.512-530, 2001.
DOI : 10.1006/jcss.2001.1774
URL : http://doi.org/10.1006/jcss.2001.1774

F. Kammer and T. Tholey, Approximate tree decompositions of planar graphs in linear time, Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, pp.683-698, 2012.

P. N. Klein and D. Marx, Solving Planar k -Terminal Cut in $O(n^{c \sqrt{k}})$ Time, Automata, Languages, and Programming, pp.569-580, 2012.
DOI : 10.1007/978-3-642-31594-7_48

P. N. Klein and D. Marx, A subexponential parameterized algorithm for Subset TSP on planar graphs, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp.1812-1830, 2014.
DOI : 10.1137/1.9781611973402.131

J. L. Leonard, On a conjecture of Bollob??s and Erd??s, Periodica Mathematica Hungarica, vol.13, issue.3-4, pp.281-284, 1973.
DOI : 10.1007/BF02018594

D. Lokshtanov, D. Marx, and S. Saurabh, Lower bounds based on the Exponential Time Hypothesis, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, vol.84, pp.41-71, 2011.

D. Lokshtanov, S. Saurabh, and M. Wahlström, Subexponential parameterized odd cycle transversal on planar graphs, FSTTCS 2012 Schloss Dagstuhl -Leibniz-Zentrum fuer Informatik, pp.424-434, 2012.

L. Lovász, Coverings and Colorings of Hypergraphs, Proceedings of the Fourth Southeastern Conference on Combinatorics, Graph Theory, and Computing, pp.3-12, 1973.

L. Lovász, Three short proofs in graph theory, Journal of Combinatorial Theory, Series B, vol.19, issue.3, pp.269-271, 1975.
DOI : 10.1016/0095-8956(75)90089-1

V. Lozin and D. Rautenbach, On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree, SIAM Journal on Discrete Mathematics, vol.18, issue.1, pp.195-206, 2004.
DOI : 10.1137/S0895480102419755

W. Mader, Ein Extremalproblem des Zusammenhangs von Graphen, Mathematische Zeitschrift, vol.194, issue.3, pp.223-231, 1973.
DOI : 10.1007/BF01187240

W. Mader, Grad und lokaler Zusammenhang in endlichen Graphen, Mathematische Annalen, vol.194, issue.1, pp.9-11, 1973.
DOI : 10.1007/BF01432512

M. Pilipczuk, M. Pilipczuk, P. Sankowski, and E. J. 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
URL : http://arxiv.org/abs/1306.6593

B. A. Sørensen and C. Thomassen, On k-rails in graphs, Journal of Combinatorial Theory, Series B, vol.17, issue.2, pp.143-159, 1974.
DOI : 10.1016/0095-8956(74)90082-3

R. Tarjan, Depth-First Search and Linear Graph Algorithms, SIAM Journal on Computing, vol.1, issue.2, pp.146-160, 1972.
DOI : 10.1137/0201010
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.327.8418