Name
Abstract | ||
|---|---|---|
We consider edge insertion and deletion operations that increase the connectivity of a given planar straight-line graph (PSLG), while minimizing the total edge length of the output. We show that every connected PSLG G=(V,E) in general position can be augmented to a 2-connected PSLG (V,E∪E+) by adding new edges of total Euclidean length ‖E+‖<2‖E‖, and this bound is the best possible. An optimal edge set E+ can be computed in O(|V|4) time; however the problem becomes NP-hard when G is disconnected. Further, we show that there is a sequence of edge insertions and deletions that transforms a connected PSLG G=(V,E) into a planar straight-line cycle G′=(V,E′) such that ‖E′‖≤2‖MST(V)‖, and the graph remains connected with edge length below ‖E‖+‖MST(V)‖ at all stages. These bounds are the best possible. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.tcs.2018.05.031 | Theoretical Computer Science |
Keywords | DocType | Volume |
Connectivity augmentation,Planar straight-line graphs,Computational geometry | Conference | 789 |
ISSN | Citations | PageRank |
0304-3975 | 0 | 0.34 |
References | Authors | |
0 | 11 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sang Won Bae | 1 | 189 | 31.53 |
| Jean-François Baffier | 2 | 14 | 4.80 |
| Jinhee Chun | 3 | 37 | 7.57 |
| Peter Eades | 4 | 962 | 69.36 |
| Kord Eickmeyer | 5 | 28 | 6.90 |
| Luca Grilli | 6 | 125 | 12.78 |
| Seok-Hee Hong | 7 | 1057 | 91.85 |
| Matias Korman | 8 | 178 | 37.28 |
| Fabrizio Montecchiani | 9 | 261 | 37.42 |
| Ignaz Rutter | 10 | 315 | 44.45 |
| Csaba D. Tóth | 11 | 573 | 70.13 |