Approximating the Edge Length of 2-Edge Connected Planar Geometric Graphs on a Set of Points

Given a set

P

of

n

points in the plane, we solve the problems of constructing a geometric planar graph spanning

P

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

P

, respectively. First, we construct in

O

(

n

log

n

) 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

O

(

n

log

n

) time a 2-edge connected geometric planar graph spanning

P

with max edge length bounded by

$\sqrt{5}$

times the optimal, assuming that the set

P

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

O

(

n

2

) time. We also show that for

$k \in O(\sqrt{n})$

, there exists a set

P

of

n

points in the plane such that even though the Unit Disk Graph spanning

P

is

k

-vertex connected, there is no 2-edge connected geometric planar graph spanning

P

even if the length of its edges is allowed to be up to 17/16.