The first and most important thing to say is that these maps are totally non-canon. Nor are they meant to represent any kind of consensus of opinion amongst fandom. They are strictly my own interpretation of how the Trek universe is laid out.
The maps are built on a number of assumptions.
1 : The Federation in TNG times spans eight thousand light years. This is stated by Picard in First Contact. I interpret the word 'spans' to mean that the furthest any two Federation planets are from one another is eight thousand light years, rather than saying that the Federation is a circular area eight thousand light years across.
2 : Real stars are in their real locations. Strictly speaking, there is no reason to make this assumption. It's conceivable that sometime between now and Star Trek times we will discover some fundamental flaw in our methods of measuring the distances to stars, so technically the current distances cannot be considered canon. I just decided to go with the real positions out of personal choice because it helped to peg the Federation's furthest extent.
3 : The speeds described in the TNG Tech Manual, Encyclopedia, etc., while generally true, can be circumvented. Essentially this flows from the various instances we've seen of speeds and distances not matching up throughout TOS and TNG, most especially Star Trek V which involved a trip from Earth to the centre of the Galaxy which did not take the decades one would expect from the standard warp scale, and 'The Chase' in which journies of tens of thousands of light years were covered in a matter of days. Hence, I have incorporated the 'warp highways' idea described on the sci-tech warp scales entry of this site. You can find more detail there, but essentially the theory is that there are regions of space in which warp drive is much, much faster than is said in the TNG TM. For the most part these regions are long narrow corridors, hence the name.
My guiding principle was to include the minimum possible number of highways, and to make them be as stable as is possible while still being consistent with canon. By stable, I mean that ideally a highway should get no faster or slower, nor should it move around in space. This is not always possible, and there are at least two highways which have to alter pretty radically in order to work.
4 : The layout of the Federation, Cardassians, Klingons and Romulans is approximately as shown in the DS9 Technical manual.
To define the Federation in TOS, I first plotted the positions of some of the major stars mentioned in the series. Rigel, Antares and Deneb were all stated to have been visited by Kirk during his starfleet career. Deneb is the most problematic; the star lies some 3,000 light years from Earth, which at TOS warp 6 is a 28 year round trip. Hence, there needs to be a warp highway between Earth and Deneb. In order to bring the trip down to a manageable level, this would need a speed multiplier of at least 20 - 30.
Rigel was also an oft visited star in TOS, this one about 900 light years away. By the standard TOS warp formula, this would be a more than eight year round trip. Hence, for a reasonable travel time a highway with a multiplier of at least 10 would be needed.
Antares is approximately 400 light years from Earth, so to give a travel time approximately equal to that of Rigel would need a highway with a multiplier of about 5.
Canopus is another star mentioned in TOS; this one is about 230 light years from Earth.
The layout of these stars is approximately as shown below :
Sol o Canopus o
It is commonly assumed that Earth lies on the dividing line between the Alpha and Beta quadrants, and although the origin of this is rather shaky (it was supposed to explain why the Enterprise could be 'the only ship in the quadrant' on one occasion), it is now such a widespread assumption that I have gone with it as well. If we take the stars Antares, Canopus and Rigel as defining the 'eastern' edge of the Federation, then following the DS9 TM map we get positions for the Klingons and Romulans which I am using. Some other maps prefer to put these Empires within the three star boundary, so as to stick strictly to TNG TM speeds, but on my working assumptions this isn't necessary - and I find it hard to imagine how the Federation could have a significant block of space around Canopus when their two major enemies lie directly in that path.
In the first TNG episode, 'Encounter at Farpoint', the Enterprise-D visited Deneb a few hours after stardate 41153.7. According to the ships dedication plaque it was launched on 40759.5, so the trip to Deneb took a maximum of 394.2 stardate units, or approximately 144 days. This equates to an average speed of around 7,610 times that of light. Since the ships normal cruise speed is warp 6, or 392 x c, then the multiplier of the highway connecting the two would be 19.4 - which matches almost perfectly with the range generated above for a reasonable trip in Kirk's day, especially since the E-D could easily have spent a few weeks messing around at Earth before setting off to Deneb. Hence, I assume that the Earth-Deneb highway had a multiplier of approximately 25.
For Deneb to remain a frontier world while the Federation spans 8,000 light years (in line with assumption 1), we need to have a block of space extending off to one side or the other of Deneb in the TNG era, so I have done this. This also ties in somewhat with the TNG episode 'The Chase'. In this episode a Professor asks Picard to join him on an expedition, and when asked how long it would take replies :
'Three months, perhaps a year. If I had complete diplomatic access and a Starship it would be a matter of weeks, but as it is we'll only have my shuttle and whatever arrangements we can make with transports.'
Later he shows Picard their intended route on a map of the galaxy. I have superimposed the route in red on the image below :
The final point shown on this route is Indri VIII, described as their 'first stop'. Assuming a 40,000 light year radius for the galaxy, Galen is planning to travel at least 30,000 light years to his first stop! In order to minimize the speed we can assume that the subsequent stops are very close to the first, but even if we ignore the subsequent stops altogether we get speeds that are way above those of the TNG TM. After Galen's death, Picard takes the Enterprise to Indri VIII at warp 7. No specific journey time is given but the Stardate of this episode is 46731.5 and that of the next ('Frame of Mind') is 46778.1, a gap of only 46.6 stardate units, or 17 days. In addition, when Troi tries to stress the importance of the conference they were heading to before diverting to Indri VII, Picard says he is quite prepared to inconvenience a few squabbling delegates for 'a few days'.
Even assuming that they cut the corner that Galen was forced to make this represents a trip of some 25,000 light years in a matter of 3 or 4 days, an average speed of over two and a quarter million times the speed of light! When setting off on the trip Riker ordered warp 7, which is 656 x c on the TNG scale, so we have a multiplier of at least 3,480. Galen's route seems to be an extension of the Deneb highway, since Deneb would lie approximately on the initial leg of the red line on the map. Indri VIII was said to have been discovered in 2340, so we can assume that this highway route opened up just about this time.
The highway which extended to the galactic core in ST V has apparently vanished by TNG times, or Voyager would be heading for the core rather than taking the long way back. I have assumed that this was the same thing as the Antares highway, and that it kind of 'snapped back' like a broken rubber band when it went. The far end then wandered a little over towards Cardassian space, opening these areas up to the Federation more and thus justifying the first contacts with the Cardassians and Ferengi which took place in or prior to TNG.
The galactic map shown here is about as canon as I can make it - it's taken directly from a vidcap of Voyager's astrometrics lab in 'Year of Hell', so this does indeed represent the most accurate picture possible of the Star Trek galaxy!
The most notable features are Voyager's course, which is as shown in the same episode. This defines the location of Federation space and the caretaker's array relative to the rest of the galaxy. Borg space is designed so that a nearly 10,000 light year wide strip crosses Voyager's path, so as to match up with Kes's gift of a 9,500 light year boost throwing them clear of Borg space in 'The Gift'. Yet the many subsequent encounters with the Borg indicate that Voyager is rarely far from their space, and we know that Borg space extends to within 7,000 light years of the Federation because that's where the first contact at system J25 occured.
Dominon space is in the Gamma quadrant, and is designed to be significantly larger than the Federation. The wormhole terminus is deliberately located on the edge of Dominion space to help explain why it took so long for the Dominion to react to the alpha quadrant presence in their territory.
One of the biggest problems with the warp highway theory can be summed up in the question 'why is Voyager taking so long to get home!'
But in fact, on a more careful examination Voyager not only can be accomodated, but in fact offers support for the warp highways idea. Three interesting points come out of Voyager :
1) Why wouldn't Voyager use the highway Kirk took to the centre of the galaxy in ST V? Even if it extended little past the core, it would cut their trip in half!
2) What few references there are to the ships average cruise speed put it around warp 6, which at 392 x c is indeed the Federation standard. Yet the ship is consistently said to be averaging 1,000 times the speed of light even excluding occasional jumps.
3) The Caretaker's array is almost directly opposite the Federation, approximately on the Gamma/Delta quadrant border. Yet the ship's course, as seen in 'Year of
Hell', is NOT a straight line back to the Federation. In fact, they are describing a curve which misses the centre of the galaxy. Why?
To answer these in turn :
1) The highways are, presumably somewhat unstable. I've already assumed that a really fast one opened up prior to TNG to explain the E-D's trip to Indri VIII. So I assume that the TOS highway to the core vanished sometime between TOS and TNG.
2) I have long suspected that highways are somewhat difficult to find and use, hence justifying all those mapping missions that Starships conduct. So Voyager wouldn't necessarily be able to find really good, high speed highways. Yet they can, apparently, find areas of space where the speed is 2 or 3 times higher than normal. Hence the speed problem is solved.
3) There's no real reason for Voyager to avoid the core. Kirk went there in ST V and the E-D went there in 'The N'th Degree', so there is nothing inherently dangerous about the region. But if Voyager can scan for areas some two or three times faster than normal, then their course would be a compromise which balances the advantage you get from 'riding the rapids' with the additional distance you have to travel. The curve you see in 'Year of Hell' is that compromise.