2016/12/14 by Akitaya, Hugo A., Inkulu, Rajasekhar, Nichols, Torrie L. +3 · 1 citation
#05C40 #05C85 #68R10 #Computational Geometry (cs.CG) #FOS: Computer and information sciences #I.3.5
paper · doi:10.48550/arxiv.1612.04780
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, 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‖\rm MST(V)‖, and the graph remains connected with edge length below ‖E‖+‖\rm MST(V)‖ at all stages. These bounds are the best possible.