Cerebral arteriovenous malformation (AVM) presents a great health threat due to its high probability of rupture which can cause severe brain damage or even death. For planing of embolization procedure of an AVM, the accurate knowledge of the location and size of the malformation is of utmost importance. We propose in this paper a novel AVM delineation approach using ordered thinning-based skeletonization. The main contribution is a new method for creating the graph-type skeleton from the result of the ordered skeletonization, and an automatic method for AVM detection and extraction. The main idea in our work is to use the structural (anatomical) vessel differences and the inhomogeneities in distribution of pixel gray values to locate and extract the AVM. The algorithm takes the segmentation result as an input to perform AVM delineation. It determines the AVM region automatically, without any user interaction, independently of the used segmentation algorithm. The proposed approach is validated on brain blood vessel CTA images before and after embolization. The results obtained using the Dice coefficient comparisons, the volume relative error and the AVM center position show high accuracy of our method and indicate potentials for use in surgical planning.