I just meant that the engine only needs to be able to create planar graphs - it doesn't need to be able to create all planar graphs.
Defining points on a two-dimensional grid makes checks for intersections trivial (though you're right - you can't go up to 8 edges/vertex - that was the early hour speaking).
There's your planar graph. Add enough other edges to make the game interesting, shuffle, and display. I played through level 15 today, and while I wasn't specifically looking for it, I don't remember finding any vertices which had more than 4 edges, which implies the grid. (I played through L6 just now to confirm).
I'm not positive that this is what the author's doing - just trying to point out that creating a planar graph is much easier than testing a given graph for planarity. You can make assumptions when building that you can't when analyzing.
no subject
Defining points on a two-dimensional grid makes checks for intersections trivial (though you're right - you can't go up to 8 edges/vertex - that was the early hour speaking).
There's your planar graph. Add enough other edges to make the game interesting, shuffle, and display. I played through level 15 today, and while I wasn't specifically looking for it, I don't remember finding any vertices which had more than 4 edges, which implies the grid. (I played through L6 just now to confirm).
I'm not positive that this is what the author's doing - just trying to point out that creating a planar graph is much easier than testing a given graph for planarity. You can make assumptions when building that you can't when analyzing.