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)

Citation

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.

Novelistic

Thanks! Are you sure the formula is right? On Wikipeida it says V - E + F - C = 1 for the Euler characteristic. It is, however, equivalent for C == 1. – Citation

@Citation Yes, for combinatorial hypermaps/rotation systems, there's one "infinite" face for every connected component, because the boundary of a face cannot be disconnected. – Novelistic

@Citation Put another way, Wikipedia gives the formula for topological faces, which are defined by connectivity of the space not occupied by vertices and edges. Hypermap faces are defined by permutation cycles. These coincide for connected graphs but differ slightly elsewhere. The hypermap version is much more useful for planar graph algorithms work. – Novelistic

Thanks David, searching for cycles in the dual works like a charm. Do you happen to have a reference for that? The proof is probably not too hard, but at least the direction 'every nonplanar embedding must yield such a cycle' is not trivial (or I'm stupid). Thanks! – Andreandrea

@tinLoaf The reference for interdigitating trees appears to be G. K. C. Von Staudt, "Geometrie der Lage", Nürnberg, 1847. The precise proof is going to depend on your definition of planarity. – Novelistic

@tinLoaf If you can't reply here, just email me (on my webpage; ignore the comment about SO traffic). – Novelistic