Shape features, such as protrusions or depressions on faces, and through-holes or handles, are extracted from a boundary model of a solid object, called a Generalized Edge-Face Graph (GEFG). This graph provides a face-based topological description of the object boundary. The feature identification and classification are based on the analysis of the connectivity properties of the edge-face graph associated with the GEFG and on some geometric considerations. The result is a hierarchical graph decomposition of the object boundary into components representing features.