Regular augmentation of planar graphs (Q747622)

This paper studies the problem of augmenting a planar graph such that it becomes \(k\)-regular, \(c\)-connected and remains planar, either in the sense that the augmented graph is planar, or in the sense that the input graph has a fixed (topological) planar embedding that can be extended to a planar embedding of the augmented graph. The following complexity classification of this problem for all values of \(k\) and \(c\) in both, the variable embedding and the fixed embedding case is given: (i) for \(k \leq 2\) all problems are simple, (ii) for \(k \geq 4\) all problems are NP-complete, (iii) for \(k=3\) authors provide efficient algorithms (with running time \(O(n^{1.5})\)) for deciding the existence of a \(c\)-connected, 3-regular augmentation of a graph with a fixed planar embedding for \(c=0,1,2\) and a corresponding hardness result for \(c=3\). The algorithms are such that for yes-instances a corresponding augmentation can be constructed in the same running time. NP-hardness is proven by reducing from the problem Planar3Sat.