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.

BibTeX

@Article{DiameterTreewidth_Algorithmica,
  AUTHOR        = {Erik D. Demaine and MohammadTaghi Hajiaghayi},
  TITLE         = {Diameter and Treewidth in Minor-Closed Graph Families,
                   Revisited},
  JOURNAL       = {Algorithmica},
  journalurl    = {https://www.springer.com/journal/453},
  VOLUME        = 40,
  NUMBER        = 3,
  MONTH         = {August},
  YEAR          = 2004,
  PAGES         = {211--215},

  length        = {5 pages},
  doi           = {https://dx.doi.org/10.1007/s00453-004-1106-1},
  dblp          = {https://dblp.org/rec/journals/algorithmica/DemaineH04},
  comments      = {This paper is also available from <A HREF="https://doi.org/10.1007/s00453-004-1106-1">SpringerLink</A>.},
  withstudent   = 1,
}

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]