<p>Doesn't this give you what you want?  Because you only care about the combinatorics, your problem is to embed a graph in a surface, I gather a surface of genus zero.</p>

<blockquote>
  <p>Bojan Mohar, "Embedding graphs in an arbitrary surface in linear time," <em>STOC</em> 1996 (<a href="http://dl.acm.org/citation.cfm?id=237986" rel="nofollow">ACM link</a>).</p>
</blockquote>

CC BY-SA 3.0
2012-06-18T22:58:49.297Z
I need to find a **polyhedral** embedding, if it exists.
a06e
CC BY-SA 3.0
2012-06-18T23:01:12.553Z
(See the beginning of my question for a definition of polyhedral embedding.) I think that the paper you suggest will only find an embedding in a surface of given genus, if it exists. Nothing guarantees that the embedding will be polyhedral.
a06e
CC BY-SA 3.0
2012-06-19T00:20:37.203Z
@becko: I guess I simply do not understand.  Your definition of a polyhedral embedding looks to me like an embedding in a surface. There is no geometry, just cycles and incidence.  I'll let others clear up my confusion.
Joseph O'Rourke
CC BY-SA 3.0
2012-06-19T02:54:15.567Z
@JosephO'Rourke: Faces in an embedding don't have to be simple cycles.
Timothy Sun
CC BY-SA 3.0
2012-06-19T04:21:10.403Z
@JosephO'Rourke: "Polyhedral" means the closure of every face is a closed disk, and every pair of closed faces intersects in a single edge, in a single vertex, or not at all.  Embeddings in which a single face is incident to both sides of an edge, or incident to a vertex multiple times, or in which two faces share more than one vertex, are not polyhedral.  Mohar's algorithm computes a _cellular_ embedding, meaning every face is an open disk, but that's a much weaker condition.
Jeffε
CC BY-SA 3.0
2012-06-19T11:17:58.407Z
Thanks Timothy and JeffE.  I see now.  Sorry for misunderstanding.
Joseph O'Rourke
CC BY-SA 3.0
2012-06-18T19:30:51.757Z
2012-06-18T19:30:51.757Z
Joseph O'Rourke
<p>A polyhedral embedding of a graph on a surface is an embedding without edge crossings such that all the faces are bounded by simple cycles, and any two faces share a common vertex, share a common edge, or do not intersect at all.</p>

<p>I need an algorithm that, given a graph, finds a polyhedral embedding if the graph admits it. I have been looking around but haven't found it. I also need to know the time order of the algorithm.</p>

<p>Deciding whether a graph admits a polyhedral embedding is NP-complete (proved here: B. Mohar, Existence of polyhedral embeddings of graphs, Combinatorica 21 (2001), 395–401, <a href="http://www.fmf.uni-lj.si/~mohar/Papers/Fw3npc.pdf">http://www.fmf.uni-lj.si/~mohar/Papers/Fw3npc.pdf</a>). I don't expect an efficient algorithm, just something that works.</p>

<p><strong>Note</strong>: I should mention that I am only interested in the combinatorial aspect of this problem. An embedding of a graph can be described by specifying the cyclic orderings of the edges incident on any vertex, and a signature for each edge, which is +1 or -1 according to whether the cyclic orderings of the two vertices on this edge are consistent along this edge. A face-walk is a walk in the graph where at all vertices the next edge is the leftmost edge according to the cyclic ordering on the vertex. A polyhedral embedding is an embedding where all the face-walks are simple cycles. The problem is then to find a circular ordering of edges around each edge and a signature for each edge such that all face-walks are simple cycles.</p>

CC BY-SA 3.0
2012-06-19T03:00:41.437Z
You could just enumerate all possible cyclic rotations and check whether or not the resulting embedding is polyhedral. Hey, you didn't say you had to have an efficient algorithm.
Timothy Sun
CC BY-SA 3.0
2012-06-19T03:53:30.727Z
@TimothySun We'll call that 'plan B' ;)
a06e
CC BY-SA 3.0
2012-06-19T16:25:02.243Z
does the surface have an arbitrary dimension? isnt it easier to find an embedding as the dimension of the surface goes up?
vzn
CC BY-SA 3.0
2012-06-20T03:09:49.200Z
@vzn I am refering to closed surfaces, where a surface is a compact, connected 2-manifold.
a06e
<ds.algorithms><reference-request><co.combinatorics><topological-graph-theory>
Algorithm to find a polyhedral embedding
a06e
# Algorithm to find a polyhedral embedding

(Asked by: username_0 on 2012-06-17)

A polyhedral embedding of a graph on a surface is an embedding without edge crossings such that all the faces are bounded by simple cycles, and any two faces share a common vertex, share a common edge, or do not intersect at all.

I need an algorithm that, given a graph, finds a polyhedral embedding if the graph admits it. I have been looking around but haven't found it. I also need to know the time order of the algorithm.

Deciding whether a graph admits a polyhedral embedding is NP-complete (proved here: B. Mohar, Existence of polyhedral embeddings of graphs, Combinatorica 21 (2001), 395–401, <http://www.fmf.uni-lj.si/~mohar/Papers/Fw3npc.pdf>). I don't expect an efficient algorithm, just something that works.

**Note**: I should mention that I am only interested in the combinatorial aspect of this problem. An embedding of a graph can be described by specifying the cyclic orderings of the edges incident on any vertex, and a signature for each edge, which is +1 or -1 according to whether the cyclic orderings of the two vertices on this edge are consistent along this edge. A face-walk is a walk in the graph where at all vertices the next edge is the leftmost edge according to the cyclic ordering on the vertex. A polyhedral embedding is an embedding where all the face-walks are simple cycles. The problem is then to find a circular ordering of edges around each edge and a signature for each edge such that all face-walks are simple cycles.

**Tags:** ds.algorithms, reference-request, co.combinatorics, topological-graph-theory

> **Comments:**
> **username_1**: You could just enumerate all possible cyclic rotations and check whether or not the resulting embedding is polyhedral. Hey, you didn't say you had to have an efficient algorithm.  
> **username_0**: @TimothySun We'll call that 'plan B' ;)  
> **username_2**: does the surface have an arbitrary dimension? isnt it easier to find an embedding as the dimension of the surface goes up?  
> **username_0**: @username_2 I am refering to closed surfaces, where a surface is a compact, connected 2-manifold.  

---

## 1 answers

### Answer by username_3 on 2012-06-18. Score: 2

Doesn't this give you what you want? Because you only care about the combinatorics, your problem is to embed a graph in a surface, I gather a surface of genus zero.

> Bojan Mohar, "Embedding graphs in an arbitrary surface in linear time," *STOC* 1996 ([ACM link](http://dl.acm.org/citation.cfm?id=237986)).

> **Comments:**
> **username_0**: I need to find a **polyhedral** embedding, if it exists.  
> **username_0**: (See the beginning of my question for a definition of polyhedral embedding.) I think that the paper you suggest will only find an embedding in a surface of given genus, if it exists. Nothing guarantees that the embedding will be polyhedral.  
> **username_3**: @becko: I guess I simply do not understand.  Your definition of a polyhedral embedding looks to me like an embedding in a surface. There is no geometry, just cycles and incidence.  I'll let others clear up my confusion.  
> **username_1**: @JosephO'Rourke: Faces in an embedding don't have to be simple cycles.  
> **username_4**: @JosephO'Rourke: "Polyhedral" means the closure of every face is a closed disk, and every pair of closed faces intersects in a single edge, in a single vertex, or not at all.  Embeddings in which a single face is incident to both sides of an edge, or incident to a vertex multiple times, or in which two faces share more than one vertex, are not polyhedral.  Mohar's algorithm computes a _cellular_ embedding, meaning every face is an open disk, but that's a much weaker condition.  
> **username_3**: Thanks Timothy and JeffE.  I see now.  Sorry for misunderstanding.  

---

