A linear-time algorithm for edge-disjoint paths in planar graphs |
| |
Authors: | Dorothea Wagner Karsten Weihe |
| |
Affiliation: | 1. Informatik, Universit?t Konstanz, 78434, Konstanz, Germany 2. Informatik, Universit?t Konstanz, 78434, Konstanz, Germany
|
| |
Abstract: | In this paper we discuss the problem of finding edge-disjoint paths in a planar, undirected graph such that each path connects two specified vertices on the boundary of the graph. We will focus on the “classical” case where an instance additionally fulfills the so-calledevenness-condition. The fastest algorithm for this problem known from the literature requiresO (n 5/3(loglogn)1/3) time, wheren denotes the number of vertices. In this paper now, we introduce a new approach to this problem, which results in anO(n) algorithm. The proof of correctness immediately yields an alternative proof of the Theorem of Okamura and Seymour, which states a necessary and sufficient condition for solvability. |
| |
Keywords: | 05 C 85 68 Q 35 |
本文献已被 SpringerLink 等数据库收录! |
|