Advertisement
Published in:
2010 | OriginalPaper | Chapter
Bounded Length, 2-Edge Augmentation of Geometric Planar Graphs
Authors : Evangelos Kranakis, Danny Krizanc, Oscar Morales Ponce, Ladislav Stacho
Published in: Combinatorial Optimization and Applications
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Algorithms for the construction of spanning planar subgraphs of Unit Disk Graphs (UDGs) do not ensure connectivity of the resulting graph under single edge deletion. To overcome this deficiency, in this paper we address the problem of augmenting the edge set of planar geometric graphs with straight line edges of bounded length so that the resulting graph is planar and 2-edge connected. We give bounds on the number of newly added straight-line edges and show that such edges can be of length at most 3 times the max length of the edges of the original graph; also 3 is shown to be optimal. It is shown to be NP-hard to augment a geometric planar graph to a 2-edge connected geometric planar with the minimum number of new edges of a given bounded length. Further, we prove that there is no local algorithm for augmenting a planar UDG into a 2-edge connected planar graph with straight line edges.