7
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\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
    Commented Jun 19, 2012 at 3:00
  • $\begingroup$ @TimothySun We'll call that 'plan B' ;) $\endgroup$
    – a06e
    Commented Jun 19, 2012 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
    Commented Jun 19, 2012 at 16:25
  • $\begingroup$ @vzn I am refering to closed surfaces, where a surface is a compact, connected 2-manifold. $\endgroup$
    – a06e
    Commented Jun 20, 2012 at 3:09

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ I need to find a polyhedral embedding, if it exists. $\endgroup$
    – a06e
    Commented Jun 18, 2012 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$
    – a06e
    Commented Jun 18, 2012 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
    Commented Jun 19, 2012 at 0:20
  • 1
    $\begingroup$ @JosephO'Rourke: Faces in an embedding don't have to be simple cycles. $\endgroup$
    – Timothy Sun
    Commented Jun 19, 2012 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ε
    Commented Jun 19, 2012 at 4:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.