New upper bounds on the decomposability of planar graphs
Fedor V. Fomin, Dimitrios M. Thilikos · Journal of Graph Theory · 2005
Abstract It is known that a planar graph on n vertices has branch‐width/tree‐width bounded by $\alpha \sqrt {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. © 2005 Wiley Periodicals, Inc. J Graph Theory