The Price of Connectivity Augmentation on Planar Graphs

Hugo A. Akitaya, Justin Dallant, Erik D. Demaine +5

Given two classes of graphs, ${\mathcal{G}}_1\subseteq {\mathcal{G}}_2$, and a $c$-connected graph $G\in {\mathcal{G}}_1$, we wish to augment $G$ with a smallest cardinality set of new e…