Intra-operative registration is one of the main challenges related to computer-assisted interventions. One common approach involves matching intra-operatively acquired surfaces (e.g. from a laser range scanner) to pre-operatively acquired planning data. In this paper, we propose a new method for correspondences search between surfaces, which can be used for the computation of an initial alignment. It generates graph representations and establishes correspondences by maximizing a global similarity measure. The method does not rely on landmarks or prominent surface characteristics and is independent on the initial pose of the surfaces relative to each other. According to an evaluation on a set of liver meshes, the method is able to correctly match small submeshes even in this presence of noise.