On Minimizing the Energy of a Spherical Graph Representation

Graph representations are the generalization of geometric graph drawings from the plane to higher dimensions. A method introduced by Tutte to optimize properties of graph drawings is to minimize their energy. We explore this minimization for spherical graph representations, where the vertices lie on a unit sphere such that the origin is their barycentre. We present a primal and dual semidefinite program which can be used to find such a spherical graph representation minimizing the energy. We denote the optimal value of this program by $\rho (G)$ for a given graph $G$. The value turns out to be related to the second largest eigenvalue of the adjacency matrix of $G$, which we denote by ${\lambda }_2$. We show that for $G$ regular, $\rho (G)\le \frac{{\lambda }_2}{2}\cdot v(G)$, and that equality holds if and only if the ${\lambda }_2$ eigenspace contains a spherical 1-design. Moreover, if $G$ is a random $d$-regular graph, $\rho (G)=(\sqrt{(d-1)}+o(1))\cdot v(G)$, asymptotically almost surely.