Developing routing protocols for Vehicular Ad Hoc Networks (VANETs) is a significant challenge in these large, self-organized and distributed networks. We address this challenge by studying VANETs from a network science perspective to develop solutions that act locally but influence the networkperformance globally. More specifically, we look at snapshots from highway and urban VANETs of different sizes and vehicle densities, and study parameters such as the node degree distribution, the clustering coefficient and the average shortest path length, in order to better understand the networks' structure and compare it to structures commonly found in large real world networks such as small-world and scale-free networks. We then show how to use this information to improve existing VANETprotocols. As an illustrative example, it is shown that, by adding new mechanisms that make use of this information, the overhead of the urban vehicular broadcasting (UV-CAST) protocol can be reduced substantially with no significant performance degradation.