I'm working on a "remake" of http://www.planarity.net/
Now I'm searching for a way to solve each lvl with some algorithm. Unfortunately the only thing I found with google is that a non planar star shaped polygon has to be made planar, but no algorithm. I know there is one, I've seen it about a year ago, and it was pretty "simple". When I try to figure out a solution it get's rather complicated.
Maybe one of you guys can help me?