As the buzz around location-based services (LBS) continues to grow, it’s often overlooked that for them to have any meaning there is one crucial component: A map. Today, Google signed a five-year agreement with Dutch map-maker Tele Atlas to provide maps to not only its Google Maps and Google Earth properties, but applications built on the forthcoming Google Android mobile platform as well.

With Apple’s new iPhone 3G (launching next week) gaining GPS capabilities and some big, recent Nokia purchases (U.S. map-maker Navtaq and location-based social network, Plazes), it’s clear Google’s soon-to-be rivals in the mobile space have location on the brain. Now Google does as well.

“When Google launches its Android program, Tele Atlas will provide maps for this,” said Taco Titiular, the spokesman of Tele Atlas parent company TomTom. He spoke to the Wall Street Journal.

Interesting as well is that the agreement will apparently allow Tele Atlas to get data from Google’s map users so that its maps can be improved upon. Google has a few map editing features in its programs including ‘My Maps’ and the recent ‘Map Maker’ for Google Maps as well as the ability to create new layers in Google Earth.

Terms of the deal were not disclosed.

One thing is for certain, Miss Teen South Carolina is going to be so happy (see video below).

[Check out MobileBeat, our mobile conference on July 24. Also, vote for your favorite mobile application or service company.]