New upper bounds on the decomposability of planar graphs

DOI 10.1002/jgt.20121 Abstract: It is known that a planar graph on n vertices has branch-width/ tree-width bounded by ffiffiffi n p. 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