Structural pattern recognition plays a central role in many applications. Recent advances include new theoretical results, methods and successful applications. In the present talk, some recent graph-based methods for shape analysis will be shown. The presented methods include a new representation for graph-matchingbased interactive segmentation and models for the analysis of spatial relations between objects. Applications will be presented and discussed.