Minimum weight connectivity augmentation for planar straight-line graphs

DOI10.1007/978-3-319-53925-6_16zbMATH Open1430.68171arXiv1612.04780OpenAlexW2583988881MaRDI QIDQ2980910FDOQ2980910

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)

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.

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

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

Mathematics Subject Classification ID

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

Cites Work

• A \(1.5\)-approximation algorithm for augmenting edge-connectivity of a graph from \(1\) to \(2\)
• Augmenting undirected node-connectivity by one
• Augmenting the connectivity of geometric graphs
• Optimal binary space partitions for segments in the plane
• Computing minimum length paths of a given homotopy class
• Approximation Algorithms for Several Graph Augmentation Problems
• Title not available (Why is that?)
• Connectivity augmentation in planar straight line graphs
• Planar biconnectivity augmentation with fixed embedding
• Plane geometric graph augmentation: a generic perspective
• Augmenting the connectivity of planar and geometric graphs
• Computing homotopic shortest paths in the plane
• Computing homotopic shortest paths efficiently
• 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
• Bounded length, 2-edge augmentation of geometric planar graphs
• Minimum weight connectivity augmentation for planar straight-line graphs

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)