Smart map/route drawing

The MSN Maps & Directions site features a very cool technology for displaying navigation maps in a more usable way. To try it, choose the "LineDrive" map style.

It produces results such as this:


Basically, it performs multiple layout optimizations to avoid having very short roads appear very small because of very long roads and a dumb constant scale factor. This re-ordering is performed while keeping some consistency in the layout (maintain the direction of turns , keep the correct intersections, keep the lengths ordered, and other constraints).

The "Rendering Effective Route Maps: Improving Usability Through Generalization" page (with pdf papers) goes in great details of this very interesting algorithm.

I'd also be interested in finding more details on the actual path finding (that takes place before the above mentioned optimizations). It is probably related to a "shortest path" algorithm like Dijkstra's Algorithm, but there surely are many performance issues that arise when you try to scale up like MapQuest.