Abstract. For a regular polyhedron (or polygon) centered at the origin, the coordinates of the vertices are eigenvectors of the graph Laplacian for the skeleton of that polyhedron (or polygon) associated with the first nontrivial eigenvalue. In this paper, we generalize this relationship. For a given graph, we study the eigenvalue optimization problem of maximizing the first nontrivial eigenvalue of the graph Laplacian over nonnegative edge weights. We show that the spectral realization of the graph using the eigenvectors corresponding to the solution of this problem, under certain assumptions, is a centered, unit-distance graph realization that has maximal total variance. This result gives a new method for generating unit-distance graph realizations and is based on convex duality. A drawback of this method is that the dimension of the realization is given by the multiplicity of the extremal eigenvalue, which is typically unknown prior to solving the eigenvalue optimization problem. Our results are illustrated with a number of examples.

Given a graph where vertices represent alternatives and pairwise comparison data, y_ij, is given on the edges, the statistical ranking problem is to find a potential function, defined on the vertices, such that the gradient of the potential function agrees with pairwise comparisons. We study the dependence of the statistical ranking problem on the available pairwise data, i.e., pairs (i,j) for which the pairwise comparison data y_ij is known, and propose a framework to identify data which, when augmented with the current dataset, maximally increases the Fisher information of the ranking. Under certain assumptions, the data collection problem decouples, reducing to a problem of finding an edge set on the graph (with a fixed number of edges) such that the second eigenvalue of the graph Laplacian is maximal. This reduction of the data collection problem to a spectral graph-theoretic question is one of the primary contributions of this work. As an application, we study the Yahoo! Movie user rating dataset and demonstrate that the addition of a small number of well-chosen pairwise comparisons can significantly increase the Fisher informativeness of the ranking.

We consider a general class of 2-D passive propagation media, represented as a planar graph where nodes are capacitors connected to a common ground and edges are inductors. Capacitances and inductances are fixed in time but vary in space. Kirchhoff's laws give the time dynamics of voltage and current in the system. By harmonically forcing input nodes and collecting the resulting steady-state signal at output nodes, we obtain a linear, analog device that transforms the inputs to outputs. We pose the lattice synthesis problem: given a linear transformation, find the inductances and capacitances for an inductor-capacitor circuit that can perform this transformation. Formulating this as an optimization problem, we numerically demonstrate its solvability using gradient-based methods. By solving the lattice synthesis problem for various desired transformations, we design several devices that can be used for signal processing and filtering.