Diameter and Treewidth in Minor-Closed Graph Families

1999/07/20 by David Eppstein · 11 citations
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Book embedding #Combinatorics #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Discrete mathematics #Graph #Graph minor #Line graph #Mathematics #Outerplanar graph #Partial k-tree #Pathwidth #Planar graph #Tree-depth #Treewidth #Voltage graph #math.CO #msc:05C75

paper · pdf · doi:10.1007/s004530010020

published as Algorithmica 27:275-291, 2000 · 15 pages, 12 figures

arxiv created 1999/07/20 · openalex publication_date 2000/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

It is known that any planar graph with diameter D has treewidth O(D), and this fact has been used as the basis for several planar graph algorithms. We investigate the extent to which similar relations hold in other graph families. We show that treewidth is bounded by a function of the diameter in a minor-closed family, if and only if some apex graph does not belong to the family. In particular, the O(D) bound above can be extended to bounded-genus graphs. As a consequence, we extend several approximation algorithms and exact subgraph isomorphism algorithms from planar graphs to other graph families.

Citations

• Applications of a Planar Separator Theorem
• Linear-time computation of optimal subgraphs of decomposable graphs
• Graph minors. V. Excluding a planar graph
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Approximation algorithms for NP-complete problems on planar graphs

Cited by

• Bidimensional Parameters and Local Treewidth
• Deciding first-order properties of locally tree-decomposable structures
• Linearity of grid minors in treewidth with applications through bidimensionality
• Grad and classes with bounded expansion II. Algorithmic aspects
• Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring
• Complexity of Grundy Coloring and Its Variants
• An Erdős-Pósa theorem for cycles and faces of distinct lengths
• Subgraph Isomorphism in Planar Graphs and Related Problems
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Algorithms for Graphs Embeddable with Few Crossings per Edge
• On the Complexity of Metric Dimension
• Graph minor [wikipedia]
• Treewidth [wikipedia]