A PTAS for the Sparsest 2-Spanner Problem in 4-Connected Planar

ABSTRACT: 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. 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