We propose to study the quality of CDS-based virtual backbones generated by fully distributed algorithms in mobile environments. As virtual-backbones may be used for different purposes, the importance of a characteristic may vary accordingly. In order to deal with this variety issue, we provide a set of quality criteria quantifying different suitable aspects for virtual backbones in mobile ad hoc net- works. Distributed and localized algorithms are then compared through simulations with respect to these measures and criterion-specific optimizations are proposed for the Blackbone2 algorithm.