Abstract: We consider undirected, connected graphs with nonnegative weights on the edges. Additionally, a special subset of vertices called terminals is provided as input. A graph H is said to be a distance preserving minor of G if: (i) H is a minor of G, and (ii) the distance between each pair of terminals is exactly the same in G and H. Note that the edge weights can be reassigned in H (as long as they are nonnegative). Given a family of graphs F, let f(k,F) be the minimum integer such that every graph in F with k terminals admits a distance preserving minor with at most f(k,F) vertices. We will see results for the best known bounds on the value of f for different families of graphs, namely trees, planar graphs and interval graphs.
