Minimum weight connectivity augmentation for planar straight-line graphs

DOI10.1007/978-3-319-53925-6_16MaRDI QIDQ2980910zbMATH OpenOpenAlexFDO

Authors Hugo A. Akitaya, Rajasekhar Inkulu, Torrie L. Nichols, Diane L. Souvaine, Charles R. Winston, Csaba D. Tóth

Publication date 5 May 2017

Published in WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1612.04780

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

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,Ecup{E}^{+})$ by adding new edges of total Euclidean length $|E^{+}|leq2|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^{\prime }=(V,E^{\prime })$ such that $|E^{\prime }|leq2|mMST(V)|$, and the graph remains connected with edge length below $|E|+|mMST(V)|$ at all stages. These bounds are the best possible.

Recommendations

• Minimum weight connectivity augmentation for planar straight-line graphs
• Compatible connectivity augmentation of planar disconnected graphs
• Connectivity augmentation in planar straight line graphs
• Connectivity augmentation in plane straight line graphs
• Augmenting the edge connectivity of planar straight line graphs to three

Cites work

• scientific article; zbMATH DE number 177556 (Why is no real title available?)
• A 1.5-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
• A new algorithm for computing visibility graphs of polygonal obstacles in the plane
• Approximating the edge length of 2-edge connected planar geometric graphs on a set of points
• Approximation Algorithms for Several Graph Augmentation Problems
• Augmenting the connectivity of geometric graphs
• Augmenting the connectivity of planar and geometric graphs
• Augmenting undirected node-connectivity by one
• Bounded length, 2-edge augmentation of geometric planar graphs
• Computing homotopic shortest paths efficiently
• Computing homotopic shortest paths in the plane
• Computing minimum length paths of a given homotopy class
• Connectivity augmentation in planar straight line graphs
• Minimum weight connectivity augmentation for planar straight-line graphs
• Optimal binary space partitions for segments in the plane
• Planar biconnectivity augmentation with fixed embedding
• Plane geometric graph augmentation: a generic perspective

Cited in

(7)

• Minimum weight connectivity augmentation for planar straight-line graphs
• Augmenting weighted graphs to establish directed point-to-point connectivity
• Connectivity augmentation in plane straight line graphs
• Minimum weight connectivity augmentation for planar straight-line graphs
• Tri-edge-connectivity augmentation for planar straight line graphs
• Augmenting the edge connectivity of planar straight line graphs to three
• Connectivity augmentation in planar straight line graphs

This page was built for publication: Minimum weight connectivity augmentation for planar straight-line graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2980910)