Given a triangulated surface M with arbitrary genus, the set of its cut-graphs depends on the underlying topology and the selection of a specific one should be guided by the surface geometry and targeted applications. Most of the previous work on this topic uses mesh traversal techniques for the evaluation of the geodesic metric, and therefore the cut-graphs are influenced by the mesh connectivity. Our solution is to build up the cut-graph on the iso-contours of a function f:M→R, that cut the topological handles of M, and on the completion of the cut-graph on the planar domain. In the planar domain, geodesic curves are defined by line segments whose counterparts on M, with respect to a diffeomorphism ϕ:M→R2, are smooth approximations of geodesic paths. Our method defines a family of cut-graphs of M which can target different applications, such as global parameterization with respect to different criteria (e.g., minimal length, minimization of the parameterization distortion, or interpolation of points as required by remeshing and texture mapping) or the calculation of polygonal schemes for surface classification. The proposed approach finds a cut-graph of an arbitrary triangle mesh M with n vertices and b boundary components in O((b − 1)n) time if M has 0-genus, and O(n(log(n) + 2g + b − 1)) time if g ⩾ 1. The associated polygonal schema is reduced if g = 0, and it has a constant number of redundant edges otherwise.