Paper by Erik D. Demaine

Reference:

Erik D. Demaine and MohammadTaghi Hajiaghayi, “Diameter and Treewidth in Minor-Closed Graph Families, Revisited”, Algorithmica, volume 40, number 3, August 2004, pages 211–215.

Abstract:

Eppstein [5] characterized the minor-closed graph families for which the treewidth is bounded by a function of the diameter, which includes, e.g., planar graphs. This characterization has been used as the basis for several (approximation) algorithms on such graphs (e.g., [2, 5-8]). The proof of Eppstein is complicated. In this short paper we obtain the same characterization with a simple proof. In addition, the relation between treewidth and diameter is slightly better and explicit.

Comments:

This paper is also available from SpringerLink.

Length:

The paper is 5 pages.

Availability:

The paper is available in PostScript (165k), gzipped PostScript (62k), and PDF (102k).

See information on file formats.

[Google Scholar search]