# Construction of graph embeddings with non-intersecting edges

I have a bipartite graph whose genus $g$ I know. I have a genus $g$ real surface(a $g$-holed donut). I want to construct a graph embedding on the surface so that I have no intersecting edges. Has this problem been studied before?

That is given a genus $g$ bipartite graph, provide an explicit algorithm that can embed the graph in a non-intersecting manner on to a real surface with $g$ handles.

Is there any notion of equivalence of embeddings of graphs on surfaces? If so, given a genus $g$ graph, in how many non-equivalent ways can one do the embedding?

The problem of finding the graph genus is NP-hard (the problem of determining whether an n-vertex graph has genus g is NP-complete). In this case you already know the genus.

At the same time, the graph genus problem is fixed-parameter tractable, i.e., polynomial time algorithms are known to check whether a graph can be embedded into a surface of a given fixed genus as well as to find the embedding.

-wikipedia (who writes Graph Theory wikipedia btw? Its awesome:)

If the fact that graph is bipartite doesn't play any very special role then the problem has been studied and solved.

A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface by Bojan Mohar

• David Eppstein contributes a lot to that part of Wikipedia, which explains its awesomeness ;-) – Anthony Labarre Mar 7 '11 at 21:13
• Well, in my case, I know the genus explicitly. – 1.. Mar 8 '11 at 1:58
• I totally missed the graph embedding wiki link. It will help. – 1.. Mar 8 '11 at 17:40
• If knowing the genus of the graph made the embedding problem easy, then one could determine the genus easily by just trying all n^2 possibilities. But determining the genus (even up to an approximation factor of n^ε) is NP-hard. Therefore, computing a embedding of a given graph with given genus is also NP-hard. – Jeffε Mar 9 '11 at 21:03

There is a "simpler" algorithm to check embeddability of graphs in surfaces of genus g. See this paper.

Having a bipartite graph does not help. From any graph we can obtain a bipartite version by subdividing each edge once. The embeddability of the new graph and the original one is the same.