Given a set @math of @math points in the plane, we solve the problems of constructing a geometric planar graph spanning @math 1) of minimum degree 2, and 2) which is 2-edge connected, respectively, and has max edge length bounded by a factor of 2 times the optimal; we also show that the factor 2 is best possible given appropriate connectivity conditions on the set @math , respectively. First, we construct in @math time a geometric planar graph of minimum degree 2 and max edge length bounded by 2 times the optimal. This is then used to construct in @math time a 2-edge connected geometric planar graph spanning @math with max edge length bounded by @math times the optimal, assuming that the set @math forms a connected Unit Disk Graph. Second, we prove that 2 times the optimal is always sufficient if the set of points forms a 2 edge connected Unit Disk Graph and give an algorithm that runs in @math time. We also show that for @math , there exists a set @math of @math points in the plane such that even though the Unit Disk Graph spanning @math is @math -vertex connected, there is no 2-edge connected geometric planar graph spanning @math even if the length of its edges is allowed to be up to 17 16.
A related problem is studied in @cite_2 . The authors prove that it is NP-hard to decide whether @math contains a spanning planar graph of minimum degree 2 even if @math itself has minimum degree 2. They also posed and studied the problem of finding the minimum radius @math so that @math has a geometric planar spanning subgraph of minimum degree 3 provided that @math has a spanning subgraph of minimum degree 3.
@cite_2
1844546726
An efficient heuristic is presented for the problem of finding a minimum-size k-connected spanning subgraph of an (undirected or directed) simple graph G=(V,E). There are four versions of the problem, and the approximation guarantees are as follows: minimum-size k-node connected spanning subgraph of an undirected graph 1 + [1 k], minimum-size k-node connected spanning subgraph of a directed graph 1 + [1 k], minimum-size k-edge connected spanning subgraph of an undirected graph 1+[2 (k+1)], minimum-size k-edge connected spanning subgraph of a directed graph 1 + [4 k ]. The heuristic is based on a subroutine for the degree-constrained subgraph (b-matching) problem. It is simple and deterministic and runs in time O(k|E|2). The following result on simple undirected graphs is used in the analysis: The number of edges required for augmenting a graph of minimum degree k to be k-edge connected is at most k,|V| (k+1). For undirected graphs and k=2, a (deterministic) parallel NC version of the heuristic finds a 2-node connected (or 2-edge connected) spanning subgraph whose size is within a factor of ( @math ) of minimum, where @math is a constant.