This paper proposes a new algorithm for separating a touching pair of digits by using the graphrepresentation of the pattern. The segmentation can be regarded as grouping these edges and vertices into two disconnected sub-graphs. This process is executed by applying graph theory methods and certain heuristic rules. Since the boundaries of patterns are determined along the edges, the shapes of the segmented digits can be restored with high quality. The algorithm can segment not only simply connected cases but also multiply connected ones. The results of the performance evaluation using the NIST database are also presented.