Due to climate change, earth temperatures are continuously increasing globally and this trend is even more pronounced in cities, where heat islands phenomena pose a danger to public health. At the city level, transforming part of the street surface area into green spaces may be an effective approach for mitigating this climate effect. The main objective of this work is to design new methods for reducing street surfaces under specific distances and strong connectivity constraints. The algorithms developed build Pareto Font for this bi-objective problem. They operate on directed weighted graphs derived from OpenStreetMap. The main contributions are two new algorithms, both based on betweenness centrality, the Iterative Edge Betweenness Centrality (IEBC) and Self-adaptive Iterative Edge Betweenness Centrality (S-IEBC). Ten French cities were selected for their various characteristics. In validation, the performances of the two algorithms proposed together with previous methods are compared. S-IEBC is proven superior to all previous methods.