Given a finite set of $n$ points in the unit square, I would like to find a spanning tree on these points such that the (Euclidean) distance within the tree between any pair of points is at most a constant, not dependent on $n$.
Any star graph clearly has this property, with maximum diameter $2 \sqrt 2$. However, the maximum degree of this graph is $n-1$. I would like to find such a spanning tree with smaller maximum degree.
If the spanning tree must be a line graph (degree 2), then the minimum diameter may grow as $O(\sqrt n)$, for instance on the grid graph.
If the points are not restricted to the plane, then a n-simplex requires degree $\Theta(n)$ to achieve constant diameter.
For any set of $n$ points in the unit square, does a spanning tree with constant diameter always exist with degree $o(n)$? $O(\log n)$? $O(1)$? $3$?
I would also be interested in hearing about any related research on the area of spanning trees with bounded degree in metric spaces.
Best Answer
Such a tree exists with maximum degree at most $5$. You can construct it recursively:
If there are no points in the square, you're done. If there's at least one point in the square, pick any point as the root, remove it from the set of points, divide the square into four subsquares, recursively apply the algorithm to these subsquares and the points in them, and connect the root to the at most four roots in the subsquares.
Every point has at most four children and at most one parent, so the maximum degree is $5$.
At the $k$-th level of subdivision, the square has side length $2^{-k}$, so the connections from the root to its children have length at most $2^{-k}\cdot\sqrt2$. Then we can prove by induction that the radius of the tree at the $k$-th level of subdivision is at most $2\cdot2^{-k}\cdot\sqrt2$, and hence the diameter of the tree at the $0$-th level, that is, the entire tree, is at most $2\cdot2\cdot2^0\cdot\sqrt2=2^{\frac52}$.