Packing paths in planar graphs

Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Deterministic network models in operations research (90B10)

Review text

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.

Recommendations

Cites work

Cited in

(17)

This page was built for publication: Packing paths in planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q809091)