Diameter and treewidth in minor-closed graph families

David Eppstein
Algorithmica 27:275–291, 2000
arXiv.org e-Print archive, math.CO/9907126
Mathematical Reviews 2001c:05132
http://dx.doi.org/10.1007/s004530010020

Cited by:

• Local tree-width, excluded minors, and approximation algorithms
• Deciding first order properties of locally tree-decomposable structures
• Fast approximation schemes for $K_{3,3}$-minor-free or $K_5$-minor-free graphs
• Light spanners and approximate TSP in graphs with forbidden minors
• Exponential speedup of fixed parameter algorithms on graphs excluding a graph with one crossing as a minor
• Subgraph isomorphism, log-bounded fragmentation and graphs of (locally) bounded treewidth
• Equivalence of local treewidth and linear local treewidth and its algorithmic applications
• Algorithms for Graphs of (Locally) Bounded Treewidth
• Learnability and definability in trees and similar structures
• Fixed-parameter algorithms for minor-closed graphs (of locally bounded treewidth)
• Easy Instances for Model Checking
• Bidimensional parameters and local treewidth
• Dominating sets and local treewidth
• Fixed-parameter algorithms for the $(k,r)$-center in planar graphs and map graphs
• 1.5-Approximation for treewidth of graphs excluding a graph with one crossing as a minor
• An existential locality theorem
• Computational Experiments on Graph Width Metrics
• Bidimensionality: new connections between FPT algorithms and PTASs
• Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality
• Fast algorithms for hard graph problems: bidimensionality, minors, and local treewidth
• Fixed parameter algorithms for $(k,r)$-center in planar graphs and map graphs
• Approximation algorithms via contraction decomposition