Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs

Ignasi Sau, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review


We present subexponential parameterized algorithms on planar graphs for a family of problems of the following shape: given a graph, find a connected (induced) subgraph with bounded maximum degree and with maximum number of edges (or vertices). These problems are natural generalisations of the Longest Path problem. 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.

Original languageEnglish (US)
Pages (from-to)330-338
Number of pages9
JournalJournal of Discrete Algorithms
Issue number3
StatePublished - Sep 2010


  • Bidimensionality
  • Branch decomposition
  • Catalan structures
  • Graph minors
  • Parameterized complexity
  • Planar graphs
  • Subexponential algorithm

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs'. Together they form a unique fingerprint.

Cite this