Connectivity Augmentation of Plane Graphs

We study the problem of connectivity augmentation of a planar graph, while preserving planarity. This problem is motivated by many real-world settings such as road-networks, power-networks etc. In these settings, it is crucial to preserve the original planar embedding after augmentation. In 2009, Gutwenger and Mutzel gave a constructive algorithm showing that a connected planar graph with a fixed embedding (a plane graph) can be optimally augmented to a biconnected graph without crossings while preserving the embedding. We further this line of research, by giving an algorithm that computes a minimum set of edges that makes a connected plane graph 2-edge-connected in $O(\mathrm{\mid }V\mathrm{\mid }(1+\alpha (\mathrm{\mid }V\mathrm{\mid })))$ time and linear space, where $\alpha$ is the inverse Ackermann function.