An Edge-Splitting Algorithm in Planar Graphs |
| |
Authors: | Hiroshi Nagamochi Peter Eades |
| |
Institution: | (1) Department of Information and Computer Sciences, Toyohashi University of Technology, Tempaku, Toyohashi, Aichi, 441-8580, Japan;(2) Department of Computer Science, The University of Sydney, F09—Madsen, NSW, 2006, Australia |
| |
Abstract: | 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. |
| |
Keywords: | undirected graph multigraph planar graph outerplanar graph edge-connectivity edge splitting minimum cut |
本文献已被 SpringerLink 等数据库收录! |
|