Technical Report 358-1993

Title

Non-Crossing Path Packings in Planar Graphs with Applications

Author

Karsten Weihe

Source

Download as [ps.gz]

Classification

not available

Keywords

not available

Abstract

Recently, the problem of finding non-crossing paths in planar graphs has found some interest in connection with multicommodity flows and with VLSI design. In this paper we will characterize such packings more systematically by means of topological duality. This approach is based on the well-known interrelation between shortest paths and maximum flows in planar graphs and yields efficient algorithms for those applications.