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?
