On Minimizing the Energy of a Spherical Graph Representation
share
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 ρ(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 λ_2. We show that for G regular, ρ(G) ≤λ_2/2· v(G), and that equality holds if and only if the λ_2 eigenspace contains a spherical 1-design. Moreover, if G is a random d-regular graph, ρ(G)=(√((d-1)) +o(1))· v(G), asymptotically almost surely.
READ FULL TEXT