Approximate minimum 2-connected subgraphs in weighted planar graphs

We consider the problems of finding the minimum-weight 2-connected spanning subgraph in edge-weighted planar graphs and its variations. We first give a PTAS for the problem of finding minimum-weight 2-edge-connected spanning subgraphs where duplicate edges are allowed. Then we present a new greedy spanner construction for edge-weighted planar graphs. From this we derive quasi-polynomial time approximation schemes for the problems of finding the lightest 2-edge-connected or biconnected spanning subgraph in such graphs. We also design efficient approximation schemes for the variant where vertices have non-uniform (1 or 2) connectivity constraints