Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem

Abstract

We study the sparsest cut problem when the “capacity-demand” graph is planar, and give a combinatorial polynomial 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 also prove that the sparsest cut problem is NP-hard if we only impose that the “capacity-demand” graph has no K6 minor. We use ideas that had been developed for the max-cut problem, and show how to exploit the connections among these problems.