We consider a geometric approach to graph partitioning based on the graph Beltrami energy, a discrete version of a functional that appears in classical minimal surface problems. More specifically, the optimality criterion is given by the sum of the minimal Beltrami energies of the partition components. We adapt primal-dual convex optimization methods to solve for the minimal Beltrami energy for each component of a given partition. A rearrangement algorithm is proposed to find the graph partition to minimize a relaxed version of the objective.
We also provide efficient code to solve the much faster, linearized minimal surface criterion instead (Dirichlet energy).
The toolbox includes a simple five-moons test data set (dbmoon.mat) and example code to reproduce the five-moons example.
The code is immediately based on the following two papers (to referred to as documentation and to be cited as reference):
 Dominique Zosso, Braxton Osting, "A minimal surface criterion for graph partitioning", Inverse Problems and Imaging 10(4):1149-1180, 2016. http://dx.doi.org/10.3934/ipi.2016036
and its linearized, faster version :
 Dominique Zosso, Braxton Osting, Stanley J. Osher, "A Dirichlet Energy Criterion for Graph-Based Image Segmentation", 2015 IEEE ICDM Workshop. http://dx.doi.org/10.1109/ICDMW.2015.112
Dominique Zosso (2020). MinimalSurfacePartitioning (https://www.mathworks.com/matlabcentral/fileexchange/60142-minimalsurfacepartitioning), MATLAB Central File Exchange. Retrieved .