On the complexity of the planar directed edge-disjoint paths problem
The edge-disjoint paths problem and many special cases of it are known to be NP-complete. We present a new NP-completeness result for a special case of the problem, namely the directed edge-disjoint paths problem restricted to planar supply graphs and demand graphs consisting of two sets of parallel edges.
complexity edge-disjoint paths np-completeness planar graphs integral two-commodity-flows