Several algorithms for sparsest cut (and other kinds of balanced cuts) in planar graphs have been published, like for instance:
- Finding minimum-quotient cuts in planar graphs, James K. Park, Cynthia A. Phillips, 1993
- Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem, Mourad Baïou, Francisco Barahona, 2018
- A quasipolynomial (2 + ε)-approximation for planar sparsest cut, Vincent Cohen-Addad, Anupam Gupta, Philip N. Klein, Jason Li, 2021
But I fail to find any implementation, including in graph cut libraries like KaHiP.
Does anyone have such an implementation, or explanations of why there is none?
