There was a thesis I read on automated metro map drawing which beautifully proved it's equivalence to another NP-Complete problem, and then proceeded to use a c

There was a thesis I read on automated metro map drawing which beautifully proved it's equivalence to another NP-Complete problem, and then proceeded to use a constraint solver to create locally optimal solution. Was quite a complex set of constraints. But it ended up with some good results.