Title: Covering Metric Spaces by Few Trees.

Authors: Yair Bartal, Nova Fandina and Ofer Neiman

Abstract: 
A {\em tree cover} of a metric space $(X,d)$ is a collection of trees, so that every pair $x,y\in X$ has a low distortion path in one of the trees. If it has the 
stronger property that every point $x\in X$ has a single tree with low distortion paths to all other points, we call this a {\em Ramsey} tree cover.
Tree covers and 
Ramsey tree covers have been studied by \cite[FOCS'01]{GKR04}, \cite[STOC'03]{BLMN03}, \cite[SODA'05]{CGMZ05}, \cite[FOCS'06]{MN07}, and have found several important 
algorithmic applications, e.g. routing and distance oracles. The union of trees in a tree cover also serves as a special type of spanner, that can be decomposed into 
a few trees with low distortion paths contained in a single tree; Such spanners for Euclidean pointsets were presented by \cite[FOCS'95]{ADMSS95}.

In this paper we 
devise efficient algorithms to construct tree covers and Ramsey tree covers for general, planar and doubling metrics. We pay particular attention to the desirable case 
of distortion close to 1, and study what can be achieved when the number of trees is small.  In particular, our work shows a large separation between what can be 
achieved
by tree covers vs. Ramsey tree covers.