Sparsest Cut in Planar Graphs, Maximum Concurrent Flows and Their Connections with the Max-Cut Problem

We study the sparsest cut problem when the ”capacity-demand” graph is planar, and give a combinatorial algorithm. In this type of graphs there is an edge for each positive capacity and also an edge for each positive demand. We extend this result to graphs with no K5 minor. We also show how to find a maximum concurrent flow in these two cases. We use ideas that had been developed for the max-cut problem, and show how to exploit the connections among these problems.