Packing paths in planar graphs (Q809091)

In a graph \(G=(V,E)\), k pairs of nodes \((s_ i,t_ i)\) \((i=1,...,k)\) are given. The edge-disjoint paths problem is to find k pairwise edge- disjoint paths joining the corresponding pairs \((s_ i,t_ i)\). Suppose we designate by H the graph with vertex set V and edge set \(\{s_ it_ i:\) \(i=1,...,k\}\). The above problem is NP-complete even when H just consists of two sets of parallel edges. For the special case when \(G+H\) is planar and H consists of two sets of parallel edges, P. D. Seymour gave a result. This paper generalizes Seymour's theorem: When \(G+H\) is planar and the edges of H are on at most two faces of G, the edge- disjoint paths problem has a solution if and only if certain two criteria on cut edges hold.