An Edge-Splitting Algorithm in Planar Graphs

For a multigraph G = (V, E), let s ∈ V be a designated vertex which has an even degree, and let λ G (V − s) denote min{c G(X) | Ø ≠ X ⊂ V − s}, where c G(X) denotes the size of cut X. Splitting two adjacent edges (s, u) and (s, v) means deleting these edges and adding a new edge (u, v). For an integer k, splitting two edges e 1 and e 2 incident to s is called (k, s)-feasible if λG′(V − s) ≥ k holds in the resulting graph G′. In this paper, we prove that, for a planar graph G and an even k or k = 3 with k ≤ λ 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|. However, for every odd k ≥ 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 for an outerplanar graph G and an even integer k the problem of optimally augmenting G to a k-edge-connected planar graph can be solved in O(n 3 log n) time.