Tomaz Pisanski Dept of Theoretical Comp Sci, IMFM, University of Ljubljana, Slovenia

R k, for k< n. Typically k would be 3 or 2. By posing the problem as minimising the squared norm of the appropriately weighted distance between adjacent points subject to natural normalising conditions we arrive at a formulation of the problem for which the optimal solution can be simply computed in terms of the eigenvectors of the Laplacian matrix of the (weighted) graph. For the case where the weights are chosen to be unity the solution is independent of the uniform penalty given to non-adjacent vertices. In this case and for regular graphs the technique has been applied by Pisanski 4], who demonstrated that the generated drawings are particularly pleasing in the case of Fullerene graphs arising in chemistry. The idea of using eigenvectors for drawing graphs was used rst in chemical setting for molecular orbitals; see 3]. For distance-regular graphs with a second eigenvalue of multiplicity at least k the embedding …