# 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.

-
Could you please provide some background? –  Mohammad Al-Turkistany Nov 17 '10 at 23:13
I think it is a generic question. How many handles do we need to embed a graph in a non-intersecting manner. Curious if Laplacian techniques can study this? –  Turbo Nov 17 '10 at 23:23
Thanks Arul, Could you add it to your question? –  Mohammad Al-Turkistany Nov 17 '10 at 23:37
Maybe you would be interested in a related post on MO: mathoverflow.net/questions/54395/…;. –  Hsien-Chih Chang 張顯之 Feb 5 '11 at 17:14

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.

-
Actually the error term in the formula is interesting - has a similar expression as the error term form number of primes less than a given number under the GRH. –  Turbo Nov 18 '10 at 2:48
But it does not give the estimate for genus. It provides estimate for spectral radius. –  Turbo Nov 18 '10 at 2:52
We have to use it backwards. If the spectral radius is large enough, we know the genus should be large. If you are asking upper bounds for genus, you should state it in the question. –  Hsien-Chih Chang 張顯之 Nov 18 '10 at 2:58
I thought the question was clear "...estimate the genus..." –  Turbo Nov 18 '10 at 3:23
But I thought the spectral radius is the largest eigenvalue of the adjacency matrix, which is easy to compute. All in all, this sounds like a pretty decent answer. –  Suresh Venkat Nov 18 '10 at 4:50

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.

-
Is this true for bipartite graphs too? –  Turbo Nov 18 '10 at 7:18
The hardness result must be true for bipartite graphs, since any graph can be made bipartite by introducing a new vertex on each edge. It seems really unlikely that being bipartite would help with the algorithm. –  JɛﬀE Nov 18 '10 at 14:17