5
$\begingroup$

Given a cellular embedding of a graph on a surface (by 'surface' I mean here a sphere with some $n\geq 0$ handles), one can define a dual multigraph by treating the faces of the original graph embedding as vertices and adding an edge between two vertices for every side the corresponding faces have in common in the original graph.

Here's my problem. Given a simple graph $G$, I need to find another simple graph $G'$ such that there exists a surface $S$ and a cellular embedding of $G$ on $S$ such that $G'$ is the dual of this embedding of $G$. Some simple graphs $G$ do not have simple duals on any surface (for example, a simple path; see JɛffE's comment). On the other hand, I think that for some simple graphs $G$, there can be many possible simple duals $G'$, depending on the surface and the embedding chosen.

Question: Given a simple graph $G$, give a method that finds a simple dual graph $G'$, if it exists.

None of the embeddings is required to be of minimum genus. The graphs are assumed to be connected.

$\endgroup$
  • $\begingroup$ In a previous question I asked for a method to obtain a dual multigraph. This answer provides a clear exposition of such a method. Here I am asking for a method to obtain a simple dual graph. $\endgroup$ – becko Jun 10 '12 at 0:23
  • 2
    $\begingroup$ Some graphs do not have simple duals. Consider a graph consisting of a single simple path. This graph has a unique embedding on the sphere, whose dual is a bouquet of circles (and no cellular embedding on any other surface). $\endgroup$ – Jeffε Jun 10 '12 at 2:13
  • $\begingroup$ @JɛffE Thanks. I'll try to improve the question. $\endgroup$ – becko Jun 10 '12 at 2:17
  • $\begingroup$ In general, if a graph has a vertex of degree one, there will be a loop in the dual graph, for all embeddings. $\endgroup$ – becko Jun 10 '12 at 2:25
5
$\begingroup$

For 3-regular graphs, having a simple dual is the same thing as having a polyhedral embedding (an embedding in which each face is a simple cycle and every two faces intersect in an empty set, a vertex, or an edge). But testing for the existence of a polyhedral embedding is known to be NP-complete: see B. Mohar, Existence of polyhedral embeddings of graphs, Combinatorica 21 (2001), 395–401, http://www.fmf.uni-lj.si/~mohar/Papers/Fw3npc.pdf

I'm not sure whether polyhedral embeddability is known to remain NP-complete when restricted to 3-regular graphs — it doesn't seem to be in Mohar's paper — but it seems very likely to be true.

$\endgroup$
  • $\begingroup$ I delayed marking this as the answer hoping I could get additional information from other answers. Thanks! $\endgroup$ – becko Jun 14 '12 at 3:55
  • $\begingroup$ Do you know where I can find some more information about polyhedral embeddings? Specifically, it would be nice if I could read an explanation of an algorithm that finds a polyhedral embedding of a graph if there is one. (Perhaps you know how to do it?) $\endgroup$ – becko Jun 15 '12 at 4:30
  • $\begingroup$ related: cstheory.stackexchange.com/q/11735/5982 $\endgroup$ – becko Jun 23 '12 at 3:32

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.