# Algorithm to find a polyhedral embedding

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.

• 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. Jun 19 '12 at 3:00
• @TimothySun We'll call that 'plan B' ;) Jun 19 '12 at 3:53
• does the surface have an arbitrary dimension? isnt it easier to find an embedding as the dimension of the surface goes up?
– vzn
Jun 19 '12 at 16:25
• @vzn I am refering to closed surfaces, where a surface is a compact, connected 2-manifold. Jun 20 '12 at 3:09