Cerebral arteriovenous malformation (AVM) presents a great health threat due to its high probability of rupture that can cause severe brain damage. Image segmentation alone is not sufficient to support AVM embolization procedure. In order to successfully navigate the catheter and perform embolization, the segmented blood vessels need to be classified into feeding arteries, draining veins and the AVM nidus. For this reason we address here the AVM localization and vessel decomposition problem. We propose in this paper a novel AVM localization and vessel delineation method using ordered thinning-based skeletonization. The main focus of vessel delineation is the delineation of draining veins since it is essential for the embolization procedure. The main contribution is a graph-based method for exact extraction of draining veins which, in combination with our earlier work on AVM detection, allows the AVM decomposition into veins, arteries and the nidus (with an emphasis on the draining veins). We validate the proposed approach on blood vessel phantoms representing the veins and the AVM structure, as well as on cerebral 3D digital rotational angiography (3DRA) images before and after embolization, paired with digital subtraction angiography (DSA) images. Results on AVM delineation show high correspondence to the ground truth structures and indicate potentials for use in surgical planning.