How to certify a planar embedding?

Question

I am about to implement an algorithm for calculating a planar embedding.

I have started to verify my results by running against a set of graphs (rome graphs) and comparing my results to the results of another implementation (yfiles). However, I can only check if the planar/not planar answer is equal, because for a given planar graph there may exist many different embeddings.

How can I verify that the embedding I calculated (ordering in the adjacency lists) is a correct planar embedding?

I already discovered some cases where I probably get a wrong embedding. For failing graphs usually drawing the embeddings manually gets hard. I found that the boost docs state that given any graph, one can produce a plane drawing of a graph, which will certify that the graph is planar and the certificate of planarity is easy to check. But I am also not sure if/how I can create such a drawing in a fool-proof algorithmic way from just the ordered adjacency lists.

(Btw. here's my code)

Answer 1

The easiest way that I know of is to compute an arbitrary spanning tree, then verify that the remaining edges have no cycles in the dual graph. If dnext(e) maps a half-edge e with head v to the next half-edge in counterclockwise order with head v, and sym(e) is the half-edge opposite from e, then rprev(e) = sym(dnext(e)) is the next half-edge in clockwise order with the same right face. I've implemented this approach in Algorithm.java of a project of mine: http://www.davideisenstat.com/trickle/

Alternatively, you could use Euler characteristic. Label the vertices (= cycles of the permutation dnext) and faces (= cycles of the permutation rprev) and determine how many connected components exist. Verify that (V - C) + (F - C) = E.