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.

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

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).

  • 1
    $\begingroup$ I need to find a polyhedral embedding, if it exists. $\endgroup$
    – becko
    Jun 18 '12 at 22:58
  • $\begingroup$ (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. $\endgroup$
    – becko
    Jun 18 '12 at 23:01
  • $\begingroup$ @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. $\endgroup$ Jun 19 '12 at 0:20
  • 1
    $\begingroup$ @JosephO'Rourke: Faces in an embedding don't have to be simple cycles. $\endgroup$ Jun 19 '12 at 2:54
  • 2
    $\begingroup$ @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. $\endgroup$
    – Jeffε
    Jun 19 '12 at 4:21

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.