Diameter and Treewidth in Minor-Closed Graph Families

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.

15 pages, 12 figures

Cited by in corpus (53)

• High-dimensional structure estimation in Ising models: Local separation criterion
• Planar graphs have bounded queue-number
• A Survey on Graph Drawing Beyond Planarity
• The h-Index of a Graph and its Application to Dynamic Subgraph Statistics
• Layered Separators in Minor-Closed Graph Classes with Applications
• On Low Tree-Depth Decompositions
• A complexity dichotomy for Matching Cut in (bipartite) graphs of fixed diameter
• Tree-width and dimension
• Clustered 3-Colouring Graphs of Bounded Degree
• (Meta) Kernelization
• Extended h-Index Parameterized Data Structures for Computing Dynamic Subgraph Statistics
• Nonrepetitive Colourings of Planar Graphs with $O(\log n)$ Colours
• Minors and dimension
• Computational topology of graphs on surfaces
• Minor-closed graph classes with bounded layered pathwidth
• Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask)
• Packing Topological Minors Half-Integrally
• Obstructions to a small hyperbolicity in Helly graphs
• Faster Approximation Schemes and Parameterized Algorithms on H-Minor-Free and Odd-Minor-Free Graphs
• Sparsity and dimension
• Diameter computation on $H$-minor free graphs and graphs of bounded (distance) VC-dimension
• Bidimensionality, Map Graphs, and Grid Minors
• A story of diameter, radius and Helly property
• Orthogonal Tree Decompositions of Graphs
• FPT algorithms to recognize well covered graphs
• Settling SETH vs. Approximate Sparse Directed Unweighted Diameter (up to (NU)NSETH)
• More Compact Oracles for Approximate Distances in Planar Graphs
• Optimal dynamic program for r-domination problems over tree decompositions
• Stochastic Combinatorial Optimization under Probabilistic Constraints
• Graph Pricing Problem on Bounded Treewidth, Bounded Genus and k-partite graphs
• Improved Approximation Algorithms for Projection Games
• Testing first-order properties for subclasses of sparse graphs
• NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs
• Large induced acyclic and outerplanar subgraphs of 2-outerplanar graph
• Deciding first-order properties of locally tree-decomposable structures
• Deciding first order logic properties of matroids
• On Algorithms for $L$-bounded Cut Problem
• The odd Hadwiger's conjecture is "almost'' decidable
• Parameterized Algorithms for Partial Cover Problems
• Sublinear separators, fragility and subexponential expansion
• Parametric Graph Templates: Properties and Algorithms
• Local tree-width, excluded minors, and approximation algorithms
• Pliability and Approximating Max-CSPs
• Approximate Counting for Spin Systems in Sub-Quadratic Time
• A $2^{O(k)}n$ algorithm for $k$-cycle in minor-closed graph families
• The degree-diameter problem for sparse graph classes
• The Complexity of Two Graph Orientation Problems
• Problems parameterized by treewidth tractable in single exponential time: a logical approach
• Parameterized Complexity of Firefighting Revisited
• Complexity of Metric Dimension on Planar Graphs
• Homomorphism Preservation on Quasi-Wide Classes
• Dynamic Generators of Topologically Embedded Graphs
• On Supergraphs Satisfying CMSO Properties