Proposed in this paper is a shape description and skeleton-graph matching algorithm based on histogram, which takes into consideration the shape variability of objects and adopts the length of skeleton branch as well as the radii of the disks at skeleton points as the features to describe the object shape. In the investigation,first,a method to describe the shape and the skeleton end nodes is presented based on the 2D histogram. Then,an improved optimal subsequence algorithm is proposed for the skeleton-graph matching. The descriptions of shape and skeleton end nodes are invariant to common non-rigid transformation. Experimental results demonstrate that the proposed algorithm can implement the skeleton-graph matching of objects with non-rigid transformations and the high-precision shape retrieval with low computational complexity.