New upper bounds on the decomposability of planar graphs

Fedor V. Fomin, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review


It is known that a planar graph on n vertices has branch-width/tree-width bounded by α√n. In many algorithmic applications, it is useful to have a small bound on the constant α. We give a proof of the best, so far, upper bound for the constant α, In particular, for the case of tree-width, α < 3.182 and for the case of branch-width, α < 2.122. Our proof is based on the planar separation theorem of Alon, Seymour, and Thomas and some min-max theorems of Robertson and Seymour from the graph minors series. We also discuss some algorithmic consequences of this result.

Original languageEnglish (US)
Pages (from-to)53-81
Number of pages29
JournalJournal of Graph Theory
Issue number1
StatePublished - Jan 2006


  • Branch-width
  • Parameterized algorithms
  • Planar graphs
  • Separation theorems
  • Subexponential algorithms
  • Tree-width

ASJC Scopus subject areas

  • Geometry and Topology


Dive into the research topics of 'New upper bounds on the decomposability of planar graphs'. Together they form a unique fingerprint.

Cite this