We address the problem of estimating graph eigenvalues in terms of eigenvalue location, by which we mean determining the number of eigenvalues of a symmetric matrix that lie in any given real interval.

Our algorithms are based on diagonalizing matrices and rely on Sylvester’s Law of Inertia. They are either designed for graphs in a particular class, and exploit some special feature of this class, or they rely on a structural decomposition of the input graph.

We show how a simple linear-time tree algorithm can be extended to symmetric matrices whose underlying graph has a tree decomposition of small width. We also describe how a linear-time cograph algorithm can be extended to matrices whose underlying graph has small clique-width.

These algorithms have applications that go beyond estimating eigenvalues of a particular graph, and allow us to obtain properties of an entire class. We illustrate this with applications to the solution of relevant problems in Spectral Graph Theory.