Suppose that I have a graph $G = (V,E)$, given as an incidence matrix of edges and vertices. Suppose that $G$ is planar, that is, it can be embedded in the plane without edge crossings.

I would like to construct in the combinatorial map corresponding to some (any) planar embedding.

That is, corresponding to each planar embedding $i : G \to \mathbb{R}^2$, there is a system of darts (half edges), with a fixed point free involution (corresponding to reversing the direction of a dart) and a permutation (corresponding to cyclically rotating through the darts which share the same head). This is the combinatorial map representation of the embedding $i$.

This is the representation of $G$ that I want to construct from the incidence matrix representation of $G$ in polynomial time.

I know (unless I'm misunderstanding the references) that there are a lot of algorithms that solve this problem in linear time. However, they are all very complicated.

Is there a simple algorithm (perhaps very inefficient) that shows that this construction takes polynomial time?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.