What is an algorithm for minimizing some D distances between N items?

Question

A classmate printed out a diagram of a database for class, the kind with lines representing relationships between tables. However, his lines crossed all over the place and it looked ugly.

So I got to thinking about a way to move the tables to minimize the total line distance, and I couldn't think of a way to do it, other than just moving them all on top of each other. So basically: Given N items on some 2d coordinate space and some amount of connections between pairs of those items, how do you move the items so that the total distance between pairs is minimal, but that no distance is smaller than S? (so that the tables would not be too close together) Is there some algorithm for this?

(I realize that smallest total distance won't necessarily make the layout less ugly; lines might still cross. But the table layout is just what got me thinking)

Answer 1

Hi,

Some hints:

http://en.wikipedia.org/wiki/Graph_drawing

http://en.wikipedia.org/wiki/Force-based_algorithms

Database schema diagram is a case of graph (or could be tree depending on your schema).

Cheers