Subexponential Parameterized Algorithms for Bounded-Degree Connected Subgraph Problems on Planar Graphs.

Abstract: We present subexponential parameterized algorithms on planar graphs for a family of problems that consist in, given a graph G, finding a connected (induced) subgraph H with bounded maximum degree, while maximising the number of edges (or vertices) of H. These problems are natural generalisations of Longest Path. Our approach uses bidimensionality theory combined with novel dynamic programming techniques over branch decompositions of the input graph. These techniques can be applied to a more general family of problems that deal with finding connected subgraphs under certain degree constraints. [Copyright &y& Elsevier]