# How to compute the genus of a Graph?

What's the simplest way to compute the genus of a graph using Mathematica? I have looked for a Genus function (even in the Combinatorica package), but I don't think there is one.

Note: Efficiency is not an issue for the moment. I am asking for a way to compute the genus, any way, preferably a simple way.

-
Related: mathematica.stackexchange.com/q/5381/5 It probably doesn't work for Graph objects, but maybe you could adapt it for your use –  rm -rf Jun 3 '12 at 2:27
Can you point point to some algorithms? BTW, some built-in data have this information: GraphData[{"Complete", 12}, "Genus"] or GraphData["IcosahedralGraph", "Genus"]. And for some classes there are analytic closed formulas: mathworld.wolfram.com/GraphGenus.html –  Vitaliy Kaurov Jun 3 '12 at 4:07
@VitaliyKaurov I know there are algorithms for this, but they are complicated and it will take me some time learn them. I was hoping that using some of Mathematica already implemented methods could ease the job. For instance, my first thought was that Mathematica would have a Genus method somewhere, but that didn't work :) –  becko Jun 5 '12 at 2:57
Have you seen this article? –  Ｊ. Ｍ. Sep 9 '12 at 17:57
@J.M. I had not seen it. Thanks for pointing it out. –  becko Sep 10 '12 at 21:28