A PTAS for the sparsest 2-spanner of 4-connected planar triangulations

A t-spanner of an undirected, unweighted graph G is a spanning subgraph S of G with the added property that for every pair of vertices in G, the distance between them in S is at most t times the distance between them in G. We are interested in finding a sparsest t-spanner, i.e., a t-spanner with the minimum number of edges. In the general setting, this problem is known to be NP-hard for all t ≥ 2. For t ≥ 5, the problem remains NP-hard for planar graphs, whereas for t ∈ {2, 3, 4}, the complexity of this problem on planar graphs is still unknown. In this paper we present a polynomial time approximation scheme for the problem of finding a sparsest 2-spanner of a 4-connected planar triangulation.