Technical Report 324-1992

Title

The Vertex-Disjoint Menger Problem in Planar Graphs

Authors

Heike Ripphausen-Lipa, Dorothea Wagner, and Karsten Weihe

Publication

Proc. of 4th ACM-SIAM Symposium on Discrete Algorithms (SODA'93), 1993, pp. 112-119

Source

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

Classification

not available

Keywords

not available

Abstract

A linear time algorithm for finding the maximum number of vertex-disjoint paths between vertices s and t in a planar graph is presented. For general undirected graphs this problem is usually solved by applying flow techniques. These lead to an `cal O(n^3over 2) resp. cal O(kn)` algorithm for planar graphs, where k is the maximum number of (s,t)-paths. (In this paper k is not assumed to be fixed.) The best previously known algorithm for the planar case is based on a divide-and-conquer approach and has time complexity cal O(nlog n). The approach used here is completely different from all previously known methods. Using this linear time algorithm, we show that the vertex-disjoint two-face Steiner tree problem in planar graphs can be solved in linear time as well.