Paper by Erik D. Demaine

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.

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.

This paper is also available from SpringerLink.

The paper is 5 pages.

The paper is available in PostScript (165k), gzipped PostScript (62k), and PDF (102k).
See information on file formats.
[Google Scholar search]

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated July 23, 2024 by Erik Demaine.