In this paper we propose a new, graph-based approach to glacier segmentation and flowline extraction. The method, which requires a set of glacier contours and a Digital Elevation Model (DEM), consists in finding an optimum branching that connects a set of vertices belonging to the topological skeleton of each glacier. First, the challenges associated with glacier flowline extraction are presented. Then, the three main steps of the method are described: the skeleton extraction and pruning algorithm, the definition and computation of a travel cost between all pairs of skeleton vertices, and the identification of the directed minimum spanning tree in the resulting directed graph. The method, which is mainly designed for valley glaciers, is applied to glaciers in Switzerland.