A software package of algorithms and heuristics for disjoint paths in Planar Networks

We present a package for algorithms on planar networks. This package comes with a graphical user interface, which may be used for demonstrating and an imating algorithms. Our focus so far has been on disjoint path problems. Ho wever, the package is intended to serve as a general framework, wherein alg orithms for various problems on planar networks may be integrated and visua lized. For this aim, the structure of the package is designed so that integ ration of new algorithms and even new algorithmic problems amounts to apply ing a short "recipe." The package has been used to develop new variations o f well-known disjoint path algorithms, which heuristically optimize additio nal N P-hard objectives such as the total length of all paths. We will prov e that the problem of finding edge-disjoint paths of minimum total length i n a planar graph is N P-hard, even if all terminals lie on the outer face, the Eulerian condition is fulfilled, and the maximum degree is four. Finall y, as a demonstration how PlaNet can be used as a tool for developing new h euristics for N P-hard problems, we will report on results of experimental studies on efficient heuristics for this problem. (C) 1999 Elsevier Science B.V. All rights reserved.