5
$\begingroup$

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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • 4
    $\begingroup$ David Eppstein contributes a lot to that part of Wikipedia, which explains its awesomeness ;-) $\endgroup$
    – Anthony Labarre
    Mar 7, 2011 at 21:13
  • $\begingroup$ Well, in my case, I know the genus explicitly. $\endgroup$
    – Turbo
    Mar 8, 2011 at 1:58
  • $\begingroup$ I totally missed the graph embedding wiki link. It will help. $\endgroup$
    – Turbo
    Mar 8, 2011 at 17:40
  • 1
    $\begingroup$ 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. $\endgroup$
    – Jeffε
    Mar 9, 2011 at 21:03
6
$\begingroup$

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.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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