[eru]

Good luck. The problem may be NP complete in general.

[shrughes]

Well, for the cases on planarity.net, it seems O(n) to me. Or maybe something like O(n log n)

[gjm11]

It's O(n) in the general case, so certainly also for the special cases on planarity.net.

[eru]

Could you give me a source or the name of the algorithm, that allows this running time?

[gjm11]

The Wikipedia article on planarity testing cites, for instance, this paper: http://jgaa.info/accepted/2004/BoyerMyrvold2004.8.3.pdf which describes a not-insanely-complicated algorithm that constructs planar embeddings (or proves they don't exist) in linear time.

[eru]

P.S. I found a O(n) running time for planarity testing - but not embedding.