We consider the problem of multicommodity flows in planar graphs. Okamura and Seymour showed that if all the demands are incident on one face, then the cut-condition is sufficient for routing demands. We consider the following generalization of this setting and prove an approximate max flow-min cut theorem: for every demand edge, there exists a face containing both its end points. We show that the cut-condition is sufficient for routing $\Omega(1)$-fraction of all the demands. To prove this, we give a $L_1$-embedding of the planar metric which approximately preserves distance between all pair of points on the same face.
翻译:我们从平面图中考虑多种商品流动的问题。 Okamura 和 Seymour 显示,如果所有需求都发生在一个面孔上,那么截断条件就足以满足路由需求。我们考虑对这一环境作以下的概括,并证明它有一个大致最大流量-最小剪切的定理:对于每一个需求边缘,都有一个包含其两个终点的面孔。我们显示,截断条件足以解决所有需求。为了证明这一点,我们给出了一张1美元的平面图,大致保持了同一面板上所有两点之间的距离。