Abstract
In a graph G, a spanning tree T is said to be a tree t-spanner of the graph G if the distance between any two vertices in T is at most t times their distance in G. The tree t-spanner has many applications in networks and distributed environments. In this paper, we present an algorithm to find a tree 4-spanner on trapezoid graphs in O(n) time, where n is the number of vertices.
Acknowledgements
The authors are grateful to the referee for his/her suggestions in improving the quality and presentation of the paper.