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  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
Last updated August 19, 2022 by