Generating computational anatomical models of cerebrovascular networks is vital for improving clinical practice and understanding brain oxygen transport. This is achieved by extracting graph-based representations based on pre-mapping of vascular structures. Recent graphing methods can provide smooth vessels trajectories and well-connected vascular topology. However, they require water-tight surface meshes as inputs. Furthermore, adding vessels radii information on their graph compartments restricts their alignment along vascular centerlines. Here, we propose a novel graphing scheme that works with relaxed input requirements and intrinsically captures vessel radii information. The proposed approach is based on deforming geometric graphs constructed within vascular boundaries. Under a laplacian optimization framework, we assign affinity weights on the initial geometry that drives its iterative contraction toward vessels centerlines. We present a mechanism to decimate graph structure at each run and a convergence criterion to stop the process. A refinement technique is then introduced to obtain final vascular models. Our implementation is available on https://github.com/Damseh/VascularGraph. We benchmarked our results with that obtained using other efficient and state-of-the-art graphing schemes, validating on both synthetic and real angiograms acquired with different imaging modalities. The experiments indicate that the proposed scheme produces the lowest geometric and topological error rates on various angiograms. Furthermore, it surpasses other techniques in providing representative models that capture all anatomical aspects of vascular structures.