2005/09/28 by Fedor V. Fomin, Dimitrios M. Thilikos · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Optimization and Search Problems #Mathematics #Combinatorics #Planar graph #Upper and lower bounds #Bounded function #Graph #Discrete mathematics #Constant (computer programming) #Book embedding #1-planar graph #Chordal graph #Computer science
paper · doi:10.1002/jgt.20121
openalex publication_date 2005/09/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/05/21
Abstract 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. © 2005 Wiley Periodicals, Inc. J Graph Theory