Расположение элементов (иконок) и размеры указать в процентах, относительно размеров всей карты. Само изображение (фоном или через img) растягивать по ширине контейнера соответственно, резиновым. Думаю ничего сложного в данном методе нет. На мобильных, если не хочется ужимать карту, чтобы все хорошо читалось и просматривалось, можно сделать overflow: auto для контейнера, а самой карте какие-то размеры, можно будет её скролить внутри контейнера.