The traveling salesman problem is to find, given a number of cities, the shortest route that travels trhough each city exactly once and brings the salesman back to the departure point at the end of the tour. Solving this problem becomes MUCH harder as the number of cities increases; this figure shows the solution for the 13,509 cities and towns in the US that have more than 500 residents.
Traveling salesman problems and many other problems involving huge graphs need to be understood or solved efficiently to get a handle on large data networks.
Figure credit: David Applegate, Robert Bixby, Vasek Chvatal and William Cook.
URL for the figure below and other pictures illustrating the history of the Traveling Salesman Problem: http://www.keck.caam.rice.edu/tsp/history.html
See also http://www.caida.org/tools/measurement/skitter/Images/isps9808u.gif for a (very large!) graph showing Internet providers and the connectivity of their networks.
