Geometrically constrained clustering

The Facebook Friend Wheel is an interesting optimization problem, and it is surprising it can be solved in quadratic time as the developer claims. I think the statement of the problem is, given a graph, find the permutation of nodes around the edge of the wheel that minimizes the total length of the edges connecting the nodes. This makes clusters. A generalization is to place points around different shapes, for example, two circles ("your inner circle of friends"), a sphere (your Friend World on which you can see "continents" of clusters of friends), or even a hypersphere or torus.