They could make a graffiti permit, charge for it of course, and encourage folks to color the city with an artistic flair. Such a permit could lay down some guidelines and give direction to the art. A politician could make a lot of extra revenue that way. Perhaps concrete spaces could be divided up and permits bought and sold. Companies could buy commercial permits allowing them to put all that wasted billboard space to use. These permits would cost more. And of course a permit holder would have to maintain their art just like any adopt-a-highway program.
Aside from the charge for the permit, just think of all the tax revenue a green advertising campaign could drum up for environmentally friendly mediums....of which would, of course, be required use as per the permit...which would also give you a token discount on said green products.