> Somewhat related to this, I've been toying for a while with the idea
> of hacking up something to turn pgsql schemas into ER diagrams
> readable by GNU Dia. Does anyone have pointers to an algorithm that
> could be used to arrange entities and relationships on a page with a
> minimum of crossed lines?
You should look at open-source CAD software, especially one that can do
"PCB layout". I remember I saw something like that, but I can't remember
the name. The problem you are solving is identical to chip layout problem
(maybe a bit simpler).