Department of Applied Mathematics & Physics, Kyoto Univiversity

Technical Report #97007 (September, 1997)

Edge-Splitting and Edge-Connectivity Augmentation in Planar Graphs
by Hiroshi Nagamochi and Peter Eades

Let $G=(V,E)$ be a multigraph with a designated vertex $s\in V$ which has an even degree, and let $\lambda_G(V-s)$ denote $\min\{c_G(X)\mid \emptyset\neq X\subset V-s\}$, where $c_G(X)$ denotes the size of cut $X$ (that is, the number of edges between $X$ and $V-X$). For two edges $e_1 = (s,u_1)$ and $e_2 = (s,u_2)$, we say that a graph $G'$ is obtained from $G$ by {\em splitting} $e_1$ and $e_2$ at $s$ if two edges $e_1$ and $e_2$ are replaced with a single edge $(u_1,u_2)$. A sequence of splitting two edges incident to $s$ is called {\em complete} if the resulting graph has no edge incident to $s$. For an integer $k$, splitting two edges $e_1$ and $e_2$ at $s$ is called {\em $(k,s)$-feasible} if $\lambda_{G'}(V-s)\geq k$ holds in the resulting graph. For any integer $k\leq \lambda_G(V-s)$, it is known that there always exists a complete $(k,s)$-feasible splitting. In this paper, we prove that, for a planar graph $G$ and an even $k$ or $k=3$ with $k\leq \lambda_G(V-s)$, there exists a complete $(k,s)$-feasible splitting at $s$ such that the resulting graph $G'$ is still planar, and present an $O(n^3\log n)$ time algorithm for finding such a splitting, where $n = |V|$. % and $m$ is the number of pairs of vertices between which $G$ has an edge. However, for every odd $k\geq 5$, there is a planar graph $G$ with a vertex $s$ which has no complete $(k,s)$-feasible and planarity-preserving splitting. As an application of this result, we show that the problem of augmenting the edge-connectivity of an outerplanar graph to an even integer can be solved in $O(n^3\log n)$ time.