Multicommodity flows in planar graphs

Haruko Okamura, Paul Seymour

Type: Article

Publication Date: 1981-08-01

Citations: 287

DOI: https://doi.org/10.1016/s0095-8956(81)80012-3

View Publication

Locations

Journal of Combinatorial Theory Series B - View

Similar Works

Action	Title	Year	Authors
+	Multicommodity flows in graphs	1983	Haruko Okamura
+	Non-3-crossing families and multicommodity flows	1994	P. A. Pevzner
+ PDF Chat	Maximum Flow in Directed Planar Graphs with Vertex Capacities	2009	Haim Kaplan Yahav Nussbaum
+ PDF Chat	Maximum Flow in Directed Planar Graphs with Vertex Capacities	2010	Haim Kaplan Yahav Nussbaum
+	Multicommodity network flow with jump constraints	1997	Jean‐François Maurras Yann Vaxès
+ PDF Chat	Spanning Trees in Multipartite Geometric Graphs	2017	Ahmad Biniaz Prosenjit Bose David Eppstein Anil Maheshwari Pat Morin Michiel Smid
+ PDF Chat	Non-crossing Shortest Paths Lengths in Planar Graphs in Linear Time	2023	Lorenzo Balzotti Paolo Giulio Franciosa
+	Nonoriented Multicommodity Flow Problems	2008	Pierre Chardaire Abdel Lisser
+ PDF Chat	Maximum st-Flow in Directed Planar Graphs via Shortest Paths	2013	Glencora Borradaile Anna Harutyunyan
+ PDF Chat	Monotone Drawings of Planar Graphs	2002	János Pach Gézá Tóth
+ PDF Chat	Non-crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time	2022	Lorenzo Balzotti Paolo Giulio Franciosa
+	Rerouting shortest paths in planar graphs	2016	Paul Bonsma
+ PDF Chat	A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs	2021	Rajesh Chitnis
+ PDF Chat	Multicuts in Planar and Bounded-Genus Graphs with Bounded Number of Terminals	2015	Éric Colin de Verdière
+	Multicuts in Planar and Bounded-Genus Graphs with Bounded Number of Terminals	2016	Éric Colin de Verdière
+ PDF Chat	Boundary-to-Boundary Flows in Planar Graphs	2013	Glencora Borradaile Anna Harutyunyan
+	Algorithms and bounds for drawing non-planar graphs with crossing-free subgraphs	2015	Patrizio Angelini Carla Binucci Giordano Da Lozzo Walter Didimo Luca Grilli Fabrizio Montecchiani Maurizio Patrignani Ioannis G. Tollis
+ PDF Chat	Intersection Graphs of Non-crossing Paths	2019	Steven Chaplick
+	Reducing computational effort in detecting integral multicommodity networks	1980	James R. Evans
+ PDF Chat	Vertex Disjoint Paths in Upward Planar Graphs	2014	Saeed Akhoondian Amiri Ali Golshani Stephan Kreutzer Sebastian Siebertz

Works That Cite This (61)

Action	Title	Year	Authors
+	On Canonical Concurrent Flows, Crossing Number and Graph Expansion	1994	Farhad Shahrokhi László Á. Székely
+	Embeddings of Topological Graphs: Lossy Invariants, Linearization, and 2-Sums	2008	Amit Chakrabarti Alexander Jaffe James R. Lee Justin Vincent
+ PDF Chat	Pathwidth, trees, and random embeddings	2013	James R. Lee Anastasios Sidiropoulos
+	On Odd Cuts and Plane Multicommodity Flows	1981	Paul Seymour
+	Decomposition of graphs on surfaces and a homotopic circulation theorem	1991	Alexander Schrijver
+	Min-Max Results in Combinatorial Optimization	1983	Alexander Schrijver
+ PDF Chat	Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators	2022	Guyslain Naves F. Bruce Shepherd Henry Xia
+	On multicommodity flows in planar graphs	1984	Refael Hassin
+	Flow-cut gaps for integer and fractional multiflows	2012	Chandra Chekuri F. Bruce Shepherd Christophe Weibel
+ PDF Chat	On fractional multicommodity flows and distance functions	1988	C.A.J. Hurkens Alexander Schrijver Éva Tardos

Works Cited by This (1)

Action	Title	Year	Authors
+	On Odd Cuts and Plane Multicommodity Flows	1981	Paul Seymour