4
$\begingroup$

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?

$\endgroup$

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.