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$ – Timothy Sun 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$ – Joseph O'Rourke Jun 19 '12 at 0:20
  • 1
    $\begingroup$ @JosephO'Rourke: Faces in an embedding don't have to be simple cycles. $\endgroup$ – Timothy Sun 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

