Characterising graph drawing with eigenvectors

We consider the problem of embedding a graph on n vertices in Euclidean space Rk, 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 has interesting properties see Godsil 2]. This paper demonstrates that a problem, that has been traditionally solved by gradient descent techniques used to minimise a measure of poverty of the generated embedding, a ords an analytical solution which can be