We investigate the interplay of band structure topology and localization properties of Wannier functions. To this end, we extend a recently proposed compressed sensing based paradigm for the search for maximally localized Wannier functions [Ozolins, Proc. Natl. Acad. Sci. USA 110, 18368 (2013)PNASA60027-842410.1073/pnas.1318679110]. We develop a practical toolbox that enables the search for maximally localized Wannier functions which exactly obey the underlying physical symmetries of a translationally invariant quantum lattice system under investigation. Most saliently, this allows us to systematically identify the most localized representative of a topological equivalence class of band structures, i.e., the most localized set of Wannier functions that is adiabatically connected to a generic initial representative. We also elaborate on the compressed sensing scheme and find a particularly simple and efficient implementation in which each step of the iteration is an O(NlogN) algorithm in the number of lattice sites N. We present benchmark results on one-dimensional topological superconductors demonstrating the power of these tools. Furthermore, we employ our method to address the open question of whether compact Wannier functions can exist for symmetry-protected topological states such as topological insulators in two dimensions. The existence of such functions would imply exact flat-band models with finite range hopping. Here, we find numerical evidence for the absence of such functions. We briefly discuss applications in dissipative-state preparation and in devising variational sets of states for tensor network methods.