The role of planarity in connectivity problems parameterized by treewidth

For some years, it was believed that for "connectivity" problems such as Hamiltonian Cycle, algorithms running in time 2O(tw) nO(1) -called singleexponential- existed only on planar and other sparse graph classes, where tw stands for the treewidth of the n-vertex input graph. This was recently disproved by Cygan et al. [FOCS 2011] and Bodlaender et al. [ICALP 2013], who provided single-exponential algorithms on general graphs for essentially all connectivity problems that were known to be solvable in single-exponential time on sparse graphs. During my internship, we further investigate the role of planarity in connectivity problems parameterized by treewidth, and convey that several problems can indeed be distinguished according to their behavior on planar graphs. In particular, we show that there exist problems that cannot be solved in time 2o(twlog tw) nO(1) on general graphs but that can be solved in time 2O(tw) nO(1) when restricted to planar graphs, and problems that can be solved in time 2O(twlog tw) nO(1) on general graphs but that cannot be solved in time 2o(twlog tw) nO(1) even when restricted to planar graphs, the negative results holding unless the ETH fails. We feel that our results constitute a first step in a subject that can be much exploited.