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.