min-cut-surfaces
Minimum cuts in surface graphs (tentative title). By Erin W. Chambers, Jeff Erickson, Kyle Fox, and Amir Nayyeri.
Abstract: Let G be an edge-weighted directed graph with n vertices embedded on an orientable surface of genus g. We describe algorithms to efficiently compute minimum s,t-cuts and global minimum cuts of G.
This work is based on the following conference papers:
E. W. Chambers, J. Erickson, and A. Nayyeri. Minimum cuts and shortest homologous cycles. In Proc. 25th Ann. Symp. Comput. Geom., pages 377–385, 2009.
J. Erickson, K. Fox, and A. Nayyeri. Global minimum cuts in surface embedded graphs. In Proc. 23rd Ann. ACM-SIAM Symp. Discrete Algorithms, pages 1309—1318, 2012.
J. Erickson and A. Nayyeri. Minimum cuts and shortest non-separating cycles via homology covers. In Proc. 22nd Ann. ACM-SIAM Symp. Discrete Algorithms, pages 1166–1176, 2011.