Spectral techniques for genus of a graph

Question

A generic question: are there any spectral techniques to estimate the genus of a graph? I am interested in bipartite graphs.

Answer 1

Deciding the exact bound for genus of a graph via spectral techniques may be hard, but giving an upper or lower bound seems possible. The following paper gives a way to estimate genus by the largest eigenvalue of the adjacency matrix, i.e. the spectral radius $\rho(G)$.

Spectral radius of finite and infinite planar graphs and of graphs of bounded genus, Zdenek Dvorak and Bojan Mohar, JCTB 2010.

They provide an upper bound on the spectral radius for a genus $g$ graph, as stated in the following theorem.

Theorem. For a genus $g$ graph, $\rho(G) = \sqrt{8\Delta(G)} + O(\sqrt{g} \log g)$, where $\Delta(G)$ denotes the maximum degree of graph $G$.

We can use this to estimate a lower bound for genus of a graph, if the spectral radius of the graph is large enough. For more precise bound for the big-O constant please see the paper.

The property as being a bipartite graph seems to help little here. They are able to provide a bipartite instance where the inequality on planar graphs is best possible.

Answer 2

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.