In this paper, we propose an original framework for three dimensional face representation and similarity matching. Basic traits of a face are encoded by extracting convex and concave regions from the surface of a face model. A compact graph representation is then constructed from these regions through an original modeling technique capable to quantitatively measure spatial relationships between regions in a three dimensional space and to encode this information in an attributed relational graph. In this way, the structural similarity between two face models is evaluated by matching their corresponding graphs. Experimental results on a 3D face database show that the proposed solution attains high retrieval accuracy and is reasonably robust to facial expression and pose changes.