Abstract: For curve-skeleton extraction, many methods firstly extract medial surfaces of 3D shapes, and then generate curve-skeletons from medial surfaces. Due to the details of shapes, medial surfaces are rugged in general. Hence, the obtained curve-skeletons are often rough, very possibly containing too many junction points than required, failing to represent the topology of 3D shapes concisely. In this paper, we present a novel method that is also based on medial surfaces. It employs the classical（set cover problem） SCP model to optimize the medial surfaces for reducing the interference from shape details, generating a compact and neat representation for a 3D shape, called a medial graph. Afterwards, medial graphs are used instead of medial surfaces for extracting curve skeletons, according to the contraction strategy in our current implementation. As a result, the obtained curve-skeleton is clean and compact, with suitable junction points to well represent the topological structures of 3D shapes. Another benefit is that our method can run much faster, because the medial graphs are very small in size. Experimental results show that our method can improve skeleton quality, compared to existing methods, and run much faster than them, even by three orders of magnitude.