Airports and national airline companies are often times associated with the image a country or region wants to project. More importantly, the world-wide airport network--as other critical infrastructures--has fundamental economic impact on local and national economies. For these reasons, many measures--including, total number of passengers, total number of flights, or total amount of cargo--quantifying the importance of the world airports are compiled and publicized. Here, we analyze the structure of the world-wide airport network in order to investigate its overall efficiency and growth mechanisms. We build a network of 3883 cities with airports and assign links to pairs of cities that are connected by non-stop flights. We find that the world-wide airport network is a small-world network for which (i) the number of non-stop connections from a given city, and (ii) the number of shortest paths going through a given city have distributions that decay as truncated power-laws with exponents close to -1. These results suggest that the main growth mechanism for the network is the establishment of flight connections to hubs. Our results also suggest that an increasing flight frequency prevented the formation of a star-network--a network with a single hub and many spikes--and that both the evolution toward a star-network and then to a multi-hub structure can be explained in terms of an attempt to maintain the overall efficiency of the network. Surprisingly, we also find that the most connected cities are not necessarily the most central cities, that is, the cities through which most shortest paths go. We show that this counter-intuitive result may be explained by geo-political constraints which are common to many critical infrastructures.