B. Courcelle, On the model-checking of monadic second-order formulas with edge set quantifications, Discrete Applied Mathematics, vol.160, issue.6, pp.866-887, 2012.
DOI : 10.1016/j.dam.2010.12.017

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

M. Chudnovsky, A. Scott, P. Seymour, J. Fortune, J. Hopcroft et al., Disjoint paths in tournaments The directed subgraphs homeomorphism problem, Theoretical Computer Science, vol.10, issue.3, pp.111-121, 1980.

A. Slivkins, Parameterized Tractability of Edge-Disjoint Paths on Directed Acyclic Graphs, SIAM Journal on Discrete Mathematics, vol.24, issue.1, pp.146-157, 2010.
DOI : 10.1137/070697781

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

R. Michael, F. V. Fellows, D. Fomin, F. A. Lokshtanov, S. Rosamond et al., Local search: Is brute-force avoidable?, Journal of Computer and System Sciences, vol.78, issue.3 2, pp.707-719, 2012.

J. Guo, S. Hartung, R. Niedermeier, and O. Suchy, The Parameterized Complexity of Local Search for TSP, More Refined, ISAAC, vol.2011, pp.614-623

D. Marx, Searching the k-change neighborhood for TSP is W[1]-hard, Operations Research Letters, vol.36, issue.1, pp.31-36, 2008.
DOI : 10.1016/j.orl.2007.02.008

L. Hans, M. Bodlaender, S. Cygan, J. Kratsch, and . Nederlof, Solving weighted and counting variants of connectivity problems parameterized by treewidth deterministically in single exponential time

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

D. M. Thilikos, U. Kapodistrian, and . Athens, is it possible to add at most k edges such that the resulting graph remains plane and has diameter at most k? If (G, k) is a yes instance of the above problem, and G ? is a minor of G, then (G ? , k) is also a yes instance of the same problem. From the meta-algorithmic consequence of the Graph Minors series, it follows that the above problem is fixed-parameter tractable, i.e., there exists an algorithm with running time f (k)n O(1) (see e.g. [1]). However, so far no such algorithm has been constructed. A possible approach is to use the fact that, if (G, k) is a yes instance, then G has treewidth bounded by some function of k. Then a dynamic programming algorithm for Planar Completion to Bounded Diameter on graphs of bound treewidth would result in the construction of the desired algorithm. More generally, how can we design bounded-treewidth dynamic-programming algorithms for planar completion problems? References 1

R. Michael, M. A. Fellows, and . Langston, Nonconstructive tools for proving polynomialtime decidability, Journal of the ACM, vol.35, issue.3, pp.727-739, 1988.

P. Wollan, A new proof for the weak-structure theorem with explicit constants:00] Rajesh Chitnis Approximability and fixed parameter algorithms: a new look Sang-Il Oum: Excluded vertex-minors for graphs of linear rank-width a most k Janos Makowski: Definability of numerical graph parameters and various notions of width, pp.0-10

D. Marx, The k-disjoint paths problem in directed planar graphs Paul Bonsma: Surface split decompositions: fast dynamic programming over branch decompositions for graphs of bounded genus:30] Guy Kortsarz: Tools for multicoloring with applications to planar graphs and bounded treewidth graphs, :00] Iyad A. Kanj: What makes normalized weighted satisfiability tractable? [12:15] Lunch, pp.0-1030

Y. Kobayashicamden, T. Us-stephan-kreutzer, . Berlin, K. De-o-joung-kwon, . Daejeon et al., Giannopoulou: Exclusion theorems for immersions on surface embedded graphs Packing edge-disjoint odd S-cycles in 4-edge-connected graphs Frédéric Mazoit: Tree-width of hypergraphs and surface duality [12:15] Lunch Sudeshna Kolay The Institute of Mathematical Sciences ? Chennai, Stephan Kreutzer: An excluded grid theorem for digraphs with forbidden minors, pp.0-1030