Data anonymization is a technique that uses data distortion to preserve privacy of public data to be published. Several data anonymization techniques and principles have been proposed in the past such as k-anonymity, l-diversity, and slicing. Slicing promises to address the drawbacks of the other two anonymization models. Our proposition is the use of a graph-based vertical partitioning algorithm (GBVP) in the process of Slicing instead of the originally proposed Partition Around Medoids (PAM). We will present several arguments that favor GBVP against PAM as a choice for clustering algorithm. © Springer India 2016.