Two suggestions depending on your scenario:
1) If actual linear geographical distance between the cities isn't important, then you can take your graph of connected cities and connect them by different modes of transportation, so small boats for rivers, roads for cars, train tracks, airports, etc. You can give each city different backgrounds and icons saying which is which and just tell the player they can only move between cities with the same icon. (This can also be abstractly represented with colors of numbers, only going between cities with a matching color or number)
2) If geographical realism is important (As it would be if you're trying to depict, say, the whole actual earth) then I would consider that a messy map is indicative of a game design problem, namely, that there are too many choices for the player. Therefore, I would restrict their choices using an additional game mechanic. Depending on your game's genre you could have something like Scheduled caravans or specific source->destination plane tickets, printed on cards, which the users draws and them must choose between. You can divide the board into regions, and have a separate pile for each region, thus limited the choices of travel to your desired radius, but also allowing overlaps.