The skeleton and its associated medial axis give a very compact representation of objects, even in the case of complex shapes and topologies. They are powerful shape descriptors, bridging the gap between low-level and high-level object representations. Surprisingly, skeletons have been used in a relatively small number of applications. This work deals with the question of using the potential strength of the skeleton and the medial axis. From the me-dial axis, we build adequate attributed relational graphs to organize in structured way information about object shape and topology contained in the medial axis. This representation then permits to compare in a meaningful way various objects using a graph-matching algorithm. Synthetic results are presented.