  We study the problem of low-stretch spanning trees in graphs of bounded
width: bandwidth, cutwidth, and treewidth. We show that any simple connected
graph $G$ with a linear arrangement of bandwidth $b$ can be embedded into a
distribution $\mathcal T$ of spanning trees such that the expected stretch of
each edge of $G$ is $O(b^2)$. Our proof implies a linear time algorithm for
sampling from $\mathcal T$. Therefore, we have a linear time algorithm that
finds a spanning tree of $G$ with average stretch $O(b^2)$ with high
probability. We also describe a deterministic linear-time algorithm for
computing a spanning tree of $G$ with average stretch $O(b^3)$. For graphs of
cutwidth $c$, we construct a spanning tree with stretch $O(c^2)$ in linear
time. Finally, when $G$ has treewidth $k$ we provide a dynamic programming
algorithm computing a minimum stretch spanning tree of $G$ that runs in
polynomial time with respect to the number of vertices of $G$.

Data Structures and Algorithms;Discrete Mathematics