### Abstract

Given a graph $G$ and a pair $\langle e’,e’’\rangle$ of distinct edges of $G$, an *edge-edge addition on $\langle e’,e’’\rangle$* is an operation that turns $G$ into a new graph $G’$ by subdividing edges $e’$ and $e’’$ with a dummy vertex $v’$ and $v’’$, respectively, and by adding the edge $(v’,v’’)$. In this paper, we show that any $2$-connected simple planar graph with minimum degree $\delta(G) \geq 3$ and maximum degree $\Delta(G)$ can be augmented by means of edge-edge additions to a $3$-connected planar graph $G’$ with $\delta(G’) \geq 3$ and $\Delta(G’) = \Delta(G)$, where each edge of $G$ participates in *at most one* edge-edge addition. This result is based on decomposing the input graph into its $3$-connected components via SPQR-trees and on showing the existence of a planar embedding in which edge pairs from a special set share a common face. Our proof is constructive and yields a linear-time algorithm to compute the augmented graph.

As a relevant application, we show how to exploit this augmentation technique to extend some classical NP-hardness results for bounded-degree $2$-connected planar graphs to bounded-degree $3$-connected planar graphs.

Publication

In *30th International Workshop on Combinatorial Algorithms (IWOCA 2019)*

###### Assistant Professor (RTDb)

My research interests are in Algorithm Engineering and Complexity, focused in particular on the theoretical and algorithmic challenges arising from the visualization of graphs.