Packing paths in planar graphs (Q809091)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Packing paths in planar graphs |
scientific article |
Statements
Packing paths in planar graphs (English)
0 references
1990
0 references
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.
0 references
edge-disjoint paths
0 references