A biometric template contains biometric traits belonging to a certain person, like e.g. fingerprints or the facial structure.
Especially for verification purposes such human characteristics become ever more important. In order to recognize a person by means of his biometric traits a reference template must be available, which can be stored in a database and also on a RFID chip. With regard to mobile storage media, and thus only a small amount of memory, there is a need for the compression of biometric templates. This compression may be lossy, possible errors in the recognition however should be kept as small as possible. In this Master's Thesis in particular a new approach for the compression of fingerprint templates is developed. These templates contain information about the positions and orientations of the so-called minutiae, i.e. the endings and bifurcations of the dermal papillae. In turn this information is represented in the form of points of a d-dimensional coordinate system, and thus can be conceived as nodes of a graph. Hence, the focus of this thesis lies on the study of graph-based approaches. The basic idea is to store the difference vectors between always two points instead of the minutiae. For this purpose directed spanning trees allow an efficient encoding. Hence in the course of this thesis different approaches based on specific spanning trees, like e.g. the directed minimum spanning tree, the directed minimum label spanning tree and the directed weight balanced spanning tree, have been studied, and a compression of up to approximately 20% could be achieved.