A generic question: are there any spectral techniques to estimate the genus of a graph? I am interested in bipartite graphs.
$\begingroup$
$\endgroup$
4
-
$\begingroup$ Could you please provide some background? $\endgroup$– Mohammad Al-TurkistanyNov 17, 2010 at 23:13
-
$\begingroup$ 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? $\endgroup$– TurboNov 17, 2010 at 23:23
-
$\begingroup$ Thanks Arul, Could you add it to your question? $\endgroup$– Mohammad Al-TurkistanyNov 17, 2010 at 23:37
-
$\begingroup$ Maybe you would be interested in a related post on MO: mathoverflow.net/questions/54395/…. $\endgroup$– Hsien-Chih Chang 張顯之Feb 5, 2011 at 17:14
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
13
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.
answered Nov 18, 2010 at 2:39
-
$\begingroup$ 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. $\endgroup$– TurboNov 18, 2010 at 2:48
-
$\begingroup$ But it does not give the estimate for genus. It provides estimate for spectral radius. $\endgroup$– TurboNov 18, 2010 at 2:52
-
1$\begingroup$ 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. $\endgroup$ Nov 18, 2010 at 2:58
-
$\begingroup$ I thought the question was clear "...estimate the genus..." $\endgroup$– TurboNov 18, 2010 at 3:23
-
1$\begingroup$ 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. $\endgroup$ Nov 18, 2010 at 4:50
$\begingroup$
$\endgroup$
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.
-
-
6$\begingroup$ 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. $\endgroup$– JeffεNov 18, 2010 at 14:17