Skeletal representations of 2-D shape, including shock graphs, have become increasingly popular for shape matching and object recognition. However, it is well known that skeletal structure can be unstable under minor boundary deformation, part articulation, and minor shape deformation (due to, for example, small changes in viewpoint). As a result, two very similar shapes may yield two significantly different skeletal representations which, in turn, will induce a large matching distance. Such instability occurs both at external branches as well as internal branches of the skeleton. We present a framework for the structural simplification of a shape’s skeleton which balances, in an optimization framework, the desire to reduce a skeleton’s complexity by minimizing the number of branches, with the desire to maximize the skeleton’s ability to accurately reconstruct the original shape. This optimization yields a canonical skeleton whose increased stability yields significantly improved recognition performance.