New upper bounds on the decomposability of planar graphs

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.