Algorithm for schematizing (metro) maps

Question

This is a long shot, but I thought I might try before starting the dirty work.

I've got a project to build an application which will, for a defined input stations (vertices) and lines (edges), that is, a real map of some public transportation, schematize a given map into a metro map. I've done some research on the problem and it's an NP-complete problem equivalent to the 3-SAT problem. I also have some theoretic ideas on how to generate such a map, but they aren't detailed enough.

What I'm looking for is any other existing solution of this problem, some sort of pseudo-code, some real code in (almost) any other programming language etc, anything that would reduce the time I need to spend working on the algorithm itself, which will in return give me more time to work on other aspects of the application.

If anyone has ever seen anything that can help me, I'd appreciate it very much.

Answer 1

If you google for "metro map layout problem" and "metro map line crossing" you'll find a lot of references, since it has been researched very actively in the past 10 years.

The problem seems no trivial at all, and translating the "artistic" features to mathematical constraints is seemingly one of the most difficult tasks.

Anyway here are three publications that I found interesting to start with (among many, many others):

Metro Map Layout Using Multicriteria Optimization

Line Crossing Minimization on Metro Maps

The Metro Map Layout Problem

HTH!

Answer 2

Research that's similar to your topic: http://graphics.stanford.edu/papers/routemaps/