### Abstract

Suppose that G is a graph, and (s_{i}, t_{i}) (1≤i≤k) are pairs of vertices; and that each edge has a real-valued capacity (≥0), and that q_{i}≥0 (1≤i≤k) are realvalued demands. When is there a flow for each i, between s_{i} and t_{i} and of value q_{i}, 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 s_{1},...,s_{k}, t_{1},...t k are all on the boundary of the infinite face.

Original language | English (US) |
---|---|

Pages (from-to) | 75-81 |

Number of pages | 7 |

Journal | Journal of Combinatorial Theory, Series B |

Volume | 31 |

Issue number | 1 |

DOIs | |

State | Published - Aug 1981 |

### All Science Journal Classification (ASJC) codes

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

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

## Cite this

Okamura, H., & Seymour, P. D. (1981). Multicommodity flows in planar graphs.

*Journal of Combinatorial Theory, Series B*,*31*(1), 75-81. https://doi.org/10.1016/S0095-8956(81)80012-3