Tree covers of size 2 for the Euclidean plane
Artur Bikeev, Andrey Borisovich Kupavskii, Maxim Turevskii · Society for Industrial and Applied Mathematics eBooks · 2026
For a given metric space \((P,\phi)\), a tree cover of stretch \(t\) is a collection of trees on \(P\) such that edges \((x,y)\) of trees receive length \(\phi(x,y)\), and such that for any pair of points \(u,v \in P\) there is a tree \(T\) in the collection such that the induced graph distance in \(T\) between \(u\) and \(v\) is at most \(t\phi(u,v)\). In this paper, we show that, for any set of points \(P\) on the Euclidean plane, there is a tree cover consisting of two trees and with stretch \(O(1)\). Although the problem in higher dimensions remains elusive, we manage to prove that for a slightly stronger variant of a tree cover problem we must have at least \((d+1)/2\) trees in any constant stretch tree cover in \(\mathbb{R}^d\).