Three trees suffice for a constant stretch in minor-free graphs
2026-08-13 • Data Structures and Algorithms
Data Structures and AlgorithmsComputational Geometry
AI summaryⓘ
The authors show that graphs which do not contain a fixed smaller graph H as a minor can be covered by just 3 tree structures with a guaranteed maximum stretching of distances. This matches a known minimum number of trees needed for certain grid-like graphs. They do this by linking the idea of tree covers to a geometric dimension concept called Assouad--Nagata dimension and use recent results on that dimension for minor-free graphs. Their work confirms the minimum number of trees needed while keeping distance distortion low.
H-minor-free graphstree coverconstant stretchtoroidal gridAssouad-Nagata dimensionminor-free metricsgraph minormetric spacedimension bounddistance distortion
Authors
Hung Le, Huy Pham, Cuong Than, Tuan Tran
Abstract
In this short note, we show that $H$-minor-free graphs have a tree cover with $3$ trees and constant stretch for any fixed graph $H$. The number of trees matches the recent lower bound by Chen, Tan, and Xu who showed that a toroidal grid requires at least $3$ trees for constant stretch. Our result is obtained by establishing a connection between tree covers and Assouad--Nagata dimension and then invoking the recent dimension bound for minor-free metrics by Liu.