Edit: I understand the OP is asking for 2D maps, but I decided to offer this as an alternative for anyone else who may happen by. :-)
What about a 1-D map?
The concept in a nutshell...
Consider this, your alien species have no sight. Perhaps they live at the bottom of an ocean. They may or may not possess some mental model of 2-D or 3-D, but for the purpose of composing and transferring information without sight, the only option I can think of is modulation of a serial stream of data. We have ways of doing this, the way I'm communicating with words right now is an example. Sound is another example.
So if your alien is blind, they may have some peculiar system of sounds or some nearly optimal system of conveying landmarks and instructions for navigation. Take a sentence of normal speech, this one for example. It conveys a concept, "example", an object "sentence", it has a context "navigation grammar", and meta-data "objective self-reference".
One could, in this regard, imagine a kind of grammar not used for conveying common ideas, but specifically ordered for the use of conveying spatial information, directions, or instructions for navigating, perhaps with some error correction. Note that language and grammar already have all of these qualities which have developed from hundreds of thousands of years of trial and error. Conversely, a species which has no sight, but can communicate and still needs to convey spatial information, could have as a part of the common language such mechanisms developed seamlessly into their own language.
This kind of usage may also influence the language as a whole. I won't go into detail about language studies, but there is a lot of information on the web about how the use of language shapes it's structure and grammar. There are good reasons why language is the way it is and it all boils down to the energy required to conceptualize things and communicate them. Life is an experiment in optimizing the use of energy and language is only one example.
Speculations about the structure of such a "map"...
So this kind of "map", if you would choose to call it that, is more like a set of directions than a 2-D map. And rightly so, as it is very inefficient to convey higher dimensional information in a lower dimensional format. Conversely it's much simpler and more efficient to convey lower dimensional information in a higher dimensional format. So we could think of it as a set of landmarks strung together with directions for how to proceed at each landmark. Pretty straight forward. But the interesting part is how one conveys the information. As a series of sounds, vibrations, perhaps these aliens have a mechanism for producing vibrations over the surface of their bodies, like shivers. To be more specific, sound is three dimensional, but we perceive it as a temporal series. And words are two dimensional, but we interpret them in the same way, as a temporal stream of meanings.
So to expand on the complex, temporal ( 1D ) ordered "map", think of bats. They use echo location to derive a sense of their surroundings, all from a temporal stream of sound, that which reaches their ears, and their brains parse the modulation of that sound and determine a sort of 3-D depth map where the level of detail increases as they get closer to things. For our "map" it could work the same way, but rather than being an echo, it could be encoded into the sounds. Furthermore, if these aliens have the ability to produce vibrations from most of the surface of their bodies ( consider autonomic contractions of the skin or shivers, but rather under conscious and directed control ). By controlling a series of shivers over the surface of the body, when the body is oriented in a given way, the output vibrations could be, in a way projected to produce a higher amplitude of vibration in some region of space ( or water ) near to and outside the body, or more specifically, close to the surface of the alien receiving the message.
So rather than saying "there's a rocky outcrop 100 meters ahead on your left", the alien might just say "big rock" while at the same time projecting some haptic feedback to the left side of the one listening where the haptic signal encodes information about size and distance to the rock from the current location or context on the "map". So 10 words in this way is reduced to 2 with some haptic feedback. In this way very long maps would be easier and faster to convey, they would contain a lot of information, the information would be very rich and, at least the human mind, would seem to have a easier time remembering them due to the richness of the information and the high level of abstraction.