Title | ||
---|---|---|
Approximating the edge length of 2-edge connected planar geometric graphs on a set of points |
Abstract | ||
---|---|---|
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(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 2-edge 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(n2) time. We also show that for k ∈ O(√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. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1007/978-3-642-29344-3_22 | LATIN'12 Proceedings of the 10th Latin American international conference on Theoretical Informatics |
Keywords | DocType | Volume |
connected unit disk,minimum degree,unit disk graph,geometric planar graph,2-edge connected geometric planar,connected planar geometric graph,appropriate connectivity condition,set p,max edge length,n point | Conference | abs/1112.3523 |
ISSN | Citations | PageRank |
0302-9743 | 2 | 0.41 |
References | Authors | |
13 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Stefan Dobrev | 1 | 528 | 41.68 |
Evangelos Kranakis | 2 | 3107 | 354.48 |
Danny Krizanc | 3 | 1778 | 191.04 |
Oscar Morales-Ponce | 4 | 23 | 2.89 |
Ladislav Stacho | 5 | 259 | 35.64 |