I'm working on a scripting project that boils down to graphs. The project as a whole is dealing with language/word analysis, but the math under the surface uses graphs--specifically undirected planar graphs with a minimum node degree of 2 and a maximum of 1 edge between any two nodes (edges do not cross; edge direction does not matter; every node is connected to at least two other nodes; no pair of nodes is connected more than once). The largest graph I think I'll need to work with is ~30 nodes, the smallest is a trivial 3 node triangle.

What I'd like to find is an algorithm to generate a random planar graph with the above properties. Ideally I would feed the algorithm a number of nodes, and it would output a graph with that many nodes and randomly placed edges that conform with the planarity and degree requirements.

What I've tried so far is to use Delaunay triangulation, which sort of worked, but the graphs ended up being a little too similar in appearance and structure. I also tried a stupid brute force technique of placing random nodes in a simulated physical space, then drawing edges between random nodes unless that edge intersected another edge that was already drawn. That "worked," but it was incredibly inefficient and slow for any graph with more than about 8 nodes.

Any suggestions or breadcrumbs to follow here?