20120515
Approximating the edge length of 2edge connected planar geometric graphs on a set of points
Publication
Publication
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 2edge 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(nlogn) 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(nlogn) time a 2edge connected geometric planar graph spanning P with max edge length bounded by √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 κ ∈ O(√n), there exists a set P of n points in the plane such that even though the Unit Disk Graph spanning P is κvertex connected, there is no 2edge connected geometric planar graph spanning P even if the length of its edges is allowed to be up to 17/16.
Additional Metadata  

Persistent URL  dx.doi.org/10.1007/9783642293443_22 
Citation 
Dobrev, S. (Stefan), Kranakis, E, Krizanc, D. (Danny), MoralesPonce, O. (Oscar), & Stacho, L. (Ladislav). (2012). Approximating the edge length of 2edge connected planar geometric graphs on a set of points. doi:10.1007/9783642293443_22
