✦ LIBER ✦

New upper bounds on the decomposability of planar graphs

✍ Scribed by Fedor V. Fomin; Dimitrios M. Thilikos

Publisher: John Wiley and Sons
Year: 2005
Tongue: English
Weight: 335 KB
Volume: 51
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20121

No coin nor oath required. For personal study only.

✦ Synopsis

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

📜 SIMILAR VOLUMES

Upper bounds on the sum of powers of the

Upper bounds on the sum of powers of the degrees of a simple planar graph

✍ Jochen Harant; Stanislav Jendrol; Tomáš Madaras 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 131 KB 👁 1 views

A New Upper Bound on the Cheeger Number

A New Upper Bound on the Cheeger Number of a Graph

✍ Sorin Dragomir; Elisabetta Barletta 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 117 KB

Using a technique developed by A. Nilli (1991, Discrete Math. 91, 207 210), we estimate from above the Cheeger number of a finite connected graph G of small degree (2(G) 5) admitting sufficiently distant edges. ## 2001 Academic Press Let G=(V(G), E(G)) be a finite connected graph. The Cheeger numb

New upper bounds for the chromatic numbe

New upper bounds for the chromatic number of a graph

✍ Ladislav Stacho 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 55 KB 👁 3 views

The Order Upper Bound on Parity Embeddin

The Order Upper Bound on Parity Embedding of a Graph

✍ Thomas Zaslavsky 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 398 KB

A graph 1 is parity embedded in a surface if a closed path in the graph is orientation preserving or reversing according to whether its length is even or odd. The parity demigenus of 1 is the minimum of 2&/(S) (where / is the Euler characteristic) over all surfaces S in which 1 can be parity embedde

An upper bound on the number of cliques

An upper bound on the number of cliques in a graph

✍ Martin Farber; Mihály Hujter; Zsolt Tuza 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 252 KB 👁 1 views

New upper bounds on the minimum size of

New upper bounds on the minimum size of covering designs

✍ Iliya Bluskov; Heikki Hämäläinen 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 310 KB 👁 1 views

Let D = {B1 , B2 , . . . , B b } be a finite family of k-subsets (called blocks) of a vset X(v) = {1, 2, . . . , v} (with elements called points). Then D is a (v, k, t) covering design or covering if every t-subset of X(v) is contained in at least one block of D. The number of blocks, b, is the size