Technical Report 357-1993

Title

Linear-Time Algorithms for Disjoint Two-Face Paths Problems in Planar Graphs

Authors

Heike Ripphausen-Lipa, Dorothea Wagner, and Karsten Weihe

Publication

Proc. 4th Intern. Symp. Algorithms and Computations (ISAAC '93), ed. K.W. Ng, P. Raghavan, N.V. Balasubramanian and F.Y.L. Chin, 1993, pp. 343-352

Source

Download as [ps.gz]

Classification

not available

Keywords

not available

Abstract

In this paper we present a linear-time algorithm for the vertex-disjoint Two-Face Paths Problem in planar graphs, i.~e. the problem of finding k vertex-disjoint paths between pairs of terminals which lie on two face boundaries. The algorithm is based on the idea of finding rightmost paths with a certain property in planar graphs. Using this method, a linear-time algorithm for finding vertex-disjoint paths of a certain homotopy is derived. Moreover, the algorithm is modified to solve the more general linkage problem in linear time as well.