Spectral techniques for genus of a graph A generic question: are there any spectral techniques to estimate the genus of a graph? I am interested in bipartite graphs.
It is NP-hard to approximate the genus of a graph to within an additive error of $O(n^\epsilon)$.  There are polynomial-time algorithms that compute an embeddings of genus $O(g\sqrt{n})$ or  $\max\{4g, g+4n\}$, where $g$ is the true genus and $n$ is the number of vertices.  A significantly better approximation algorithm, spectral or otherwise, would be a significant breakthrough!

See: Jianer Chen, Saroja P. Kanchi, and Arkady Kanevsky. A note on approximating graph genus.  Information Processing Letters 61(6):317–322, 1997.