An Edge-Splitting Algorithm in Planar Graphs

Hiroshi Nagamochi () and Peter Eades ()
Additional contact information
Hiroshi Nagamochi: Toyohashi University of Technology
Peter Eades: The University of Sydney

Journal of Combinatorial Optimization, 2003, vol. 7, issue 2, No 2, 137-159

Abstract: 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 (search for similar items in EconPapers)
Date: 2003
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1023/A:1024470929537 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:7:y:2003:i:2:d:10.1023_a:1024470929537

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1024470929537

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().