Today, people living in cities see up to 5000 ads per day, many on public displays. More and more of these public displays are networked and equipped with sensors, making them part of a global infrastructure that is currently emerging. Such displays provide the opportunity to create a benefit for society in the form of immersive experiences and relevant content. In this way, they can overcome the display blindness that evolved over the years. Two main reasons prevent this vision from coming true: first, public displays are stuck with traditional advertising as the driving business model. Second, no common ground exists for researchers or advertisers that outline important challenges. The main contribution of this thesis is presenting a design space for advertising on public displays that identifies important challenges - mainly from an HCI perspective. The results are envisioned to provide a basis for future research and for practitioners to shape future advertisements on public displays in a positive way.