Multicommodity flows in planar graphs

Haruko Okamura, P. D. Seymour

Research output: Contribution to journalArticlepeer-review

210 Scopus citations


Suppose that G is a graph, and (si, ti) (1≤i≤k) are pairs of vertices; and that each edge has a real-valued capacity (≥0), and that qi≥0 (1≤i≤k) are realvalued demands. When is there a flow for each i, between si and ti and of value qi, such that the total flow through each edge does not exceed its capacity? Ford and Fulkerson solved this when k=1, and Hu when k=2. We solve it for general values of k, when G is planar and can be drawn so that s1,...,sk, t1,...t k are all on the boundary of the infinite face.

Original languageEnglish (US)
Pages (from-to)75-81
Number of pages7
JournalJournal of Combinatorial Theory, Series B
Issue number1
StatePublished - Aug 1981
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'Multicommodity flows in planar graphs'. Together they form a unique fingerprint.

Cite this