<blockquote>
<p>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). <em>In this case you already know the genus.</em></p>
<p>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.</p>
</blockquote>
<p>-<a href="http://en.wikipedia.org/wiki/Graph_embedding" rel="nofollow noreferrer">wikipedia</a> (who writes Graph Theory wikipedia btw? Its awesome:)</p>
<p>If the fact that graph is bipartite doesn't play any very special role then the problem has been studied and solved.</p>
<p><a href="http://epubs.siam.org/sidma/resource/1/sjdmec/v12/i1/p6_s1?isAuthorized=no" rel="nofollow noreferrer">A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface by Bojan Mohar</a></p>

CC BY-SA 2.5
2011-03-07T21:13:33.690Z
David Eppstein contributes a lot to that part of Wikipedia, which explains its awesomeness ;-)
Anthony Labarre
CC BY-SA 2.5
2011-03-08T01:58:57.393Z
Well, in my case, I know the genus explicitly.
Turbo
CC BY-SA 2.5
2011-03-08T17:40:44.650Z
I totally missed the graph embedding wiki link. It will help.
Turbo
CC BY-SA 2.5
2011-03-09T21:03:38.753Z
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ε
CC BY-SA 2.5
2011-03-07T20:51:31.840Z
2011-03-07T20:51:31.840Z
2020-06-17T09:38:08.363Z
Pratik Deoghare
<p>There is a "simpler" algorithm to check embeddability of graphs in surfaces of genus g.
See <a href="http://dx.doi.org/10.1109/FOCS.2008.53" rel="nofollow">this paper</a>.</p>

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

CC BY-SA 2.5
2011-03-07T21:31:11.423Z
2011-03-07T21:31:11.423Z
someone
<p>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?</p>

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

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

<graph-algorithms><cg.comp-geom><graph-drawing>
Construction of graph embeddings with non-intersecting edges
Turbo
# Construction of graph embeddings with non-intersecting edges

(Asked by: username_0 on 2011-03-07)

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?

**Tags:** graph-algorithms, cg.comp-geom, graph-drawing


---

## 2 answers

### Answer by username_1 on 2011-03-07. Score: 4 | Accepted answer

> 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](http://en.wikipedia.org/wiki/Graph_embedding) (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](http://epubs.siam.org/sidma/resource/1/sjdmec/v12/i1/p6_s1?isAuthorized=no)

> **Comments:**
> **username_2**: David Eppstein contributes a lot to that part of Wikipedia, which explains its awesomeness ;-)  
> **username_0**: Well, in my case, I know the genus explicitly.  
> **username_0**: I totally missed the graph embedding wiki link. It will help.  
> **username_3**: 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.  

---

### Answer by username_4 on 2011-03-07. Score: 6

There is a "simpler" algorithm to check embeddability of graphs in surfaces of genus g.
See [this paper](http://dx.doi.org/10.1109/FOCS.2008.53).

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.


---

