Cubic Augmentation of Planar Graphs

Tanja Hartmann, Jonathan Rollin, Ignaz Rutter

In this paper we study the problem of augmenting a planar graph such that it becomes 3-regular and remains planar. We show that it is NP-hard to decide whether such an augmentation…