Dear Chris, Thanks for the pointer! That seems like a fairly large family, and between this and Qiaochu's comment it seems clear that there is only something nontrivial to say about very special graphs. I'm inclined to accept unless someone comes by soon with a miraculous pointer to a literature on relaxations.

Re Douglas: Thank you. Re Qiaochu: Interesting comment. I wouldn't be surprised if a small number of eigenvectors were essentially always enough, but am not familiar with what you mean by the `corresponding Galois group'. A quick Google search only found me articles that seemed focused on graphs with at least some symmetry. (I should also mention: Even ~log(n) is interesting to me. I'd be happy to know that for large, fairly dense graphs, there is generically freedom to fix ~10 eigenvectors! )

Re: Douglas Zare: I'm not sure. The few `classical' examples I've looked at seem to have pretty different eigenvectors. Until your question, I hadn't thought about this avenue - I thought they were of interest if you want different eigenvectors. Could you let me know any intuition about why these might be good candidates?

Thanks for the comment on multidimensional scaling. I can see that this question fits into that framework, but that framework is much broader (and seems to encompass many things we'd like to do, but which are not computationally feasible). Do you know if this particular question (or one similar to it) has been addressed?