New upper bounds on the decomposability
β
Fedor V. Fomin; Dimitrios M. Thilikos
π
Article
π
2005
π
John Wiley and Sons
π
English
β 335 KB
π 1 views
## 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 th