Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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? –  J.A 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
add comment

2 Answers 2

up vote 6 down vote accepted

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.

share|improve this answer
    
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. –  J.A Nov 18 '10 at 2:48
    
But it does not give the estimate for genus. It provides estimate for spectral radius. –  J.A Nov 18 '10 at 2:52
1  
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..." –  J.A Nov 18 '10 at 3:23
1  
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
show 8 more comments

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.

share|improve this answer
    
Is this true for bipartite graphs too? –  J.A Nov 18 '10 at 7:18
6  
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ɛffE Nov 18 '10 at 14:17
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.