Abstract. We propose an approach to graph sparsification based on the idea of preserving the smallest [Formula: see text] eigenvalues and eigenvectors of the graph Laplacian. This is motivated by the fact that small eigenvalues and their associated eigenvectors tend to be more informative of the global structure and geometry of the graph than larger eigenvalues and their eigenvectors. The set of all weighted subgraphs of a graph [Formula: see text] that have the same first [Formula: see text] eigenvalues (and eigenvectors) as [Formula: see text] is the intersection of a polyhedron with a cone of positive semidefinite matrices. We discuss the geometry of these sets and deduce the natural scale of [Formula: see text]. Various families of graphs illustrate our construction.

Abstract. We show that the eigenpolytopes of graphs are universal in the sense that every polytope, up to affine equivalence, appears as the eigenpolytope of some positively weighted graph. We next extend the theory of graphical designs, which are quadrature rules for graphs, to positively weighted graphs. Through Gale duality for polytopes, we show a bijection between graphical designs and the faces of eigenpolytopes. This bijection proves the existence of graphical designs with positive quadrature weights and upper bounds the size of a minimal graphical design. Connecting this bijection with the universality of eigenpolytopes, we establish three complexity results: It is strongly NP-complete to determine if there is a graphical design smaller than the mentioned upper bound, it is NP-hard to find a smallest graphical design, and it is #P-complete to count the number of minimal graphical designs.