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.

By: Mourad Baïou, Francisco Barahona

Published in: Lecture Notes in Computer Science, volume 9682, (no ), pages 63-76 in 2016

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to .