Maximum Edge-Disjoint Paths Problem in Planar Graphs

摘要

We give a randomized algorithm for maximum edge-disjoint paths problem (MEDP) and the minimal total length of MEDP, if the graphs are planar and all terminals lie on the outer face in the order s_1, s_2, … s_k, t_k, t_(k-1), … t_1. Moreover, if the degree of the graph is bounded by 3, the algorithm becomes deterministic and can also output the number of optimal solutions. On the other hand, we prove that the counting version of these problems are #P-hard even if restricted to planar graphs with maximum degree 3.