Generate a large random planar graph

Question

What is the most efficient way to generate a large (~ 300k vertices) random planar graph ("random" here means uniformly distrbuted)?

Answer 1

Well one method would be to try and generate a random graph which satisfies similar constraints as a planar graph (for instance, edges <= 3*vertices - 6) and check if it is planar in O(n) time using Tarjan's planarity testing algorithm. If it is not planar, generate again. Not sure how efficient this would be for 300K vertices!, though (or if it will even give you graphs with uniform probability).

There is some literature on generating planar graphs, I could find one paper here : Generating Labeled Planar Graphs which apparently has expected O(n^4) running time, and might not be worth it either. Perhaps the references there will help you track down something that might help.

Good luck!