<p>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 <strong>spectral radius</strong> $\rho(G)$.</p>

<blockquote>
  <p><a href="http://arxiv.org/abs/0907.1591" rel="nofollow">Spectral radius of finite and infinite planar graphs and of graphs of bounded genus</a>, Zdenek Dvorak and Bojan Mohar, JCTB 2010.</p>
</blockquote>

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

<blockquote>
  <p><strong>Theorem.</strong> 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$.</p>
</blockquote>

<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2010-11-18T02:48:45.810Z
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
CC BY-SA 2.5
2010-11-18T02:52:51.890Z
But it does not give the estimate for genus. It provides estimate for spectral radius.
Turbo
CC BY-SA 2.5
2010-11-18T02:58:10.023Z
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 張顯之
CC BY-SA 2.5
2010-11-18T03:23:09.837Z
I thought the question was clear "...estimate the genus..."
Turbo
CC BY-SA 2.5
2010-11-18T03:28:14.567Z
@Arul: At least it is not clear to me why you claim that a lower bound of genus in terms of spectral radius does not count as an estimate of genus based on spectral techniques.
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-18T03:32:08.963Z
Estimation typically used for giving an upper OR lower bound.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-11-18T03:55:57.843Z
"...upper or lower bound..." MISSED the lower.... Hsien is correct... but I was actually interested in a little bit more than that.. usually there are different ways to define a Laplacian... wondering if keeping genus in mind if any one has defined Laplacian... I was also curious on that part as well.
Turbo
CC BY-SA 2.5
2010-11-18T03:56:37.780Z
and misread Hsien's comment*
Turbo
CC BY-SA 2.5
2010-11-18T04:07:22.543Z
@Tsuyoshi - thank you for the notification
Turbo
CC BY-SA 2.5
2010-11-18T04:36:33.450Z
It looks like the spectral radius would itself be hard to compute. In that case, the bound may not help. Are there any other results?
Turbo
CC BY-SA 2.5
2010-11-18T04:50:03.653Z
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
CC BY-SA 2.5
2010-11-18T05:15:24.093Z
@Arul: Try to wait for another day before accepting my answer. There may be something more elegant coming up soon!!
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-11-18T05:19:26.563Z
OK. Also is it sharp when $g=1$. Note log g = 0 then. Need to look at the paper.
Turbo
CC BY-SA 2.5
2010-11-18T02:39:43.560Z
2010-11-18T02:48:15.457Z
2010-11-18T02:48:15.457Z
Hsien-Chih Chang 張顯之
<p>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!</p>

<p>See: Jianer Chen, Saroja P. Kanchi, and Arkady Kanevsky. <a href="http://dx.doi.org/10.1016/S0020-0190(97)00203-2">A note on approximating graph genus</a>.  <em>Information Processing Letters</em> 61(6):317–322, 1997.</p>

CC BY-SA 2.5
2010-11-18T07:18:37.927Z
Is this true for bipartite graphs too?
Turbo
CC BY-SA 2.5
2010-11-18T14:17:41.673Z
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.
Jeffε
CC BY-SA 2.5
2010-11-18T06:40:10.153Z
2010-11-18T06:40:10.153Z
Jeffε
<p>A generic question: are there any spectral techniques to estimate the genus of a graph? I am interested in bipartite graphs.</p>

CC BY-SA 2.5
2010-11-17T23:13:46.467Z
Could you please provide some background?
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-11-17T23:23:57.393Z
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
CC BY-SA 2.5
2010-11-17T23:37:08.240Z
Thanks Arul, Could you add it to your question?
Mohammad Al-Turkistany
CC BY-SA 2.5
2011-02-05T17:14:32.507Z
Maybe you would be interested in a related post on MO: http://mathoverflow.net/questions/54395/spectral-techniques-for-genus-of-a-graph.
Hsien-Chih Chang 張顯之
<graph-theory><co.combinatorics><spectral-graph-theory>
Spectral techniques for genus of a graph
Turbo
# Spectral techniques for genus of a graph

(Asked by: username_0 on 2010-11-17)

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

**Tags:** graph-theory, co.combinatorics, spectral-graph-theory
> **Comments:**
> **username_1**: Could you please provide some background?  
> **username_0**: 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?  
> **username_1**: Thanks Arul, Could you add it to your question?  
> **username_2**: Maybe you would be interested in a related post on MO: http://mathoverflow.net/questions/54395/spectral-techniques-for-genus-of-a-graph.  

---

## 2 answers

### Answer by username_2 on 2010-11-18. Score: 6 | Accepted answer

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](http://arxiv.org/abs/0907.1591), 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.

> **Comments:**
> **username_0**: 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.  
> **username_0**: But it does not give the estimate for genus. It provides estimate for spectral radius.  
> **username_2**: 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.  
> **username_0**: I thought the question was clear "...estimate the genus..."  
> **username_3**: @Arul: At least it is not clear to me why you claim that a lower bound of genus in terms of spectral radius does not count as an estimate of genus based on spectral techniques.  
> **username_2**: Estimation typically used for giving an upper OR lower bound.  
> **username_0**: "...upper or lower bound..." MISSED the lower.... Hsien is correct... but I was actually interested in a little bit more than that.. usually there are different ways to define a Laplacian... wondering if keeping genus in mind if any one has defined Laplacian... I was also curious on that part as well.  
> **username_0**: and misread Hsien's comment*  
> **username_0**: @Tsuyoshi - thank you for the notification  
> **username_0**: It looks like the spectral radius would itself be hard to compute. In that case, the bound may not help. Are there any other results?  
> **username_4**: 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.  
> **username_2**: @Arul: Try to wait for another day before accepting my answer. There may be something more elegant coming up soon!!  
> **username_0**: OK. Also is it sharp when $g=1$. Note log g = 0 then. Need to look at the paper.  

---

### Answer by username_5 on 2010-11-18. Score: 8

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](http://dx.doi.org/10.1016/S0020-0190(97)00203-2). *Information Processing Letters* 61(6):317–322, 1997.

> **Comments:**
> **username_0**: Is this true for bipartite graphs too?  
> **username_5**: 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.  

---

