Technical Report 344-1992

Title

A Linear Time Algorithm for Edge-Disjoint Paths in Planar Graphs

Authors

Dorothea Wagner and Karsten Weihe

Publication

Springer, Lecture Notes in Computer Science 726, Proc. of the First Annual European Symposium on Algorithms (ESA'93), ed. T. Lengauer, 1992, pp. 384-395

Journal version to appear in COMBINATORICA.

Source

The report may be requested from our secretary Gabriele Klink, email: klink@math.tu-berlin.de

Classification

not available

Keywords

not available

Abstract

In this paper we discuss the problem of finding edge-disjoint paths in a planar, undirected graph s.t. each path connects two specified vertices on the outer face boundary. We will focus on the "classical" case where an instance must additionally fulfill the so-called evenness-condition. The fastest algorithm for this problem known from the literature requires `cal O(n^5/3(loglog n)^1/3) time, where n` denotes the number of vertices. In this paper now, we introduce a new approach to this problem, which yields an `cal O(n)` algorithm. The approach can be used to formulate an alternative proof for the Theorem of Okamura & Seymour.