Google Maps (and even more so Waze which they own) already had partnerships with various brands - for example, type McDonalds into Google Maps (at least in the UK) and it has the M logo next to "see locations" as soon as you've typed Mc - so it's not such a huge stretch as you think it would be.