Title: Linear-time approximation schemes for planar minimum three-edge connected and three-vertex connected spanning subgraphs,
Abstract: We present the first polynomial-time approximation schemes, i.e., (1 +
{\epsilon})-approximation algorithm for any constant {\epsilon} > 0, for the
minimum three-edge connected spanning subgraph problem and the minimum
three-vertex connected spanning subgraph problem in undirected planar graphs.
Both the approximation schemes run in linear time.