Minimum Weight Connectivity Augmentation for Planar Straight-Line Graphs

详细信息    查看全文

• 刊名：Lecture Notes in Computer Science
• 出版年：2017
• 出版时间：2017
• 年：2017
• 卷：10167
• 期：1
• 页码：204-216
• 丛书名：WALCOM: Algorithms and Computation
• ISBN：978-3-319-53925-6
• 卷排序：10167

文摘

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\cup E^+)\) by adding new edges of total Euclidean length \(\Vert E^+\Vert \le 2\Vert E\Vert \), 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 plane cycle \(G'=(V,E')\) such that \(\Vert E'\Vert \le 2\Vert \mathrm{MST}(V)\Vert \), and the graph remains connected with edge length below \(\Vert E\Vert +\Vert \mathrm{MST}(V)\Vert \) at all stages. These bounds are the best possible.