Technical Report 371-1994

Title

Efficient Algorithms for Disjoint Paths in Planar Graphs

Authors

Heike Ripphausen-Lipa, Dorothea Wagner, and Karsten Weihe

Publication

To appear in the DIMACS volume from the special year on combinatorial optimization.

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 give a survey of algorithms for various disjoint paths problems in planar graphs, in particular for problems that have originally been motivated by VLSI-design. We will focus on problems for which realistic algorithms have been designed, that is, algorithms that can be implemented relatively easily and are guaranteed to have reasonable running times.