Edge-Disjoint Paths in Planar Graphs with Short Total Length
Ulrik Brandes, Gabriele Neyer, Dorothea Wagner · KOPS (University of Konstanz) · 1996
The problem of finding edge-disjoint paths in a planar graph such that each path connects two specified vertices on the outer face of the graph is well studied. The "classical" Eulerian case introduced by Okamura and Seymour [7] is solvable in linear time [10]. So far, the length of the paths were not considered. In this paper now, we prove that the problem of finding edge-disjoint paths of minimum total length in a planar graph is NP-hard, even if the graph fullfills the Eulerian condition and the maximum degree is four. Minimizing the length of the longest path is NP-hard as well. Efficient heuristics based on the algorithm from [10] are presented that determine edge-disjoint paths of small total length. We have implemented these heuristics and have studied their behaviour. It turns out that some of the heuristics are empirically very successful.