There are several papers written on the subject of tree spanners. One of these was entitled Tree Spanners^[1] written by mathematicians Leizhen Cai and Derek Corneil, which explored theoretical and algorithmic problems associated with tree spanners. Some of the conclusions from that paper are listed below. ${\displaystyle n}$  is always the number of vertices of the graph, and ${\displaystyle m}$  is its number of edges.

1. A tree 1-spanner, if it exists, is a minimum spanning tree and can be found in ${\displaystyle {\mathcal {O}}(m\log \beta (m,n))}$  time (in terms of complexity) for a weighted graph, where ${\displaystyle \beta (m,n)=\min \left\{i\mid \log ^{i}n\leq m/n\right\}}$ . Furthermore, every tree 1-spanner admissible weighted graph contains a unique minimum spanning tree.
2. A tree 2-spanner can be constructed in ${\displaystyle {\mathcal {O}}(m+n)}$  time, and the tree ${\displaystyle t}$ -spanner problem is NP-complete for any fixed integer ${\displaystyle t>3}$ .
3. The complexity for finding a minimum tree spanner in a digraph is ${\displaystyle {\mathcal {O}}((m+n)\cdot \alpha (m+n,n))}$ , where ${\displaystyle \alpha (m+n,n)}$  is a functional inverse of the Ackermann function
4. The minimum 1-spanner of a weighted graph can be found in ${\displaystyle {\mathcal {O}}(mn+n^{2}\log(n))}$  time.
5. For any fixed rational number ${\displaystyle t>1}$ , it is NP-complete to determine whether a weighted graph contains a tree t-spanner, even if all edge weights are positive integers.
6. A tree spanner (or a minimum tree spanner) of a digraph can be found in linear time.
7. A digraph contains at most one tree spanner.
8. The quasi-tree spanner of a weighted digraph can be found in ${\displaystyle {\mathcal {O}}(m\log \beta (m,n))}$  time.

• Graph spanner
• Geometric spanner

• Handke, Dagmar; Kortsarz, Guy (2000), "Tree spanners for subgraphs and related tree covering problems", Graph-Theoretic Concepts in Computer Science: 26th International Workshop, WG 2000 Konstanz, Germany, June 15–17, 2000, Proceedings, Lecture Notes in Computer Science, vol. 1928, pp. 206–217, doi:10.1007/3-540-40064-8_20, ISBN 978-3-540-41183-3.