Packing paths in planar graphs
type: Item
instance of: scholarly article
title: Packing paths in planar graphs
zbMATH Open document ID: 0732.05032
DOI: 10.1007/BF02128668
author: András Frank
published in: Combinatorica
publication date: 1990-01-01T00:00:00Z
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.
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 90B10
zbMATH DE Number: 4210172
zbMATH Keywords: edge-disjoint paths
reviewed by: Norman F. Quimpo
MaRDI profile type: Publication
cites work: On the Complexity of Timetable and Multicommodity Flow Problems
cites work: On the planar integer two-flow problem
cites work: On Odd Cuts and Plane Multicommodity Flows
full work available at URL: https://doi.org/10.1007/bf02128668
OpenAlex ID: W1966166008
description: scientific article; zbMATH DE number 4210172