(2) Department of Computer Science Technion--Israel Institute of Technology 32000 Haifa, Israel
A $t$-spanner of a graph $G$ is a spanning subgraph $H$ such that the distance between any two vertices in $H$ is at most $t$ times their distance in $G$. Spanners arise in the context of approximating the original graph by a sparse subgraph~\cite{peleg}. The MINIMUM $t$-SPANNER problem seeks to find a $t$-spanner with the minimum number of edges for the given graph. In this paper, we completely settle the complexity status of this problem for various values of $t$, on Chordal graphs, Split graphs, Bipartite graphs and Convex Bipartite graphs. We also give a factor two approximation algorithm for the MINIMUM 2-SPANNER problem on interval graphs. Finally, we provide approximation algorithms for the bandwidth minimization problem on Convex Bipartite graphs and Split graphs using the notion of tree spanners.