How to generate large random planar graphs?

Question

Hi coders ... I'm currently facing the problem, that I don't know how to generate random planar graphs with up to 10^5 Nodes and 10^5 Edges. My first solution was generating a random graph and check afterwoods for planarity with some libraries! But this only works for small graphs! Do you have any ideas?

Answer 1

I googled, and this paper was a short and fun read! https://users.cecs.anu.edu.au/~bdm/papers/plantri-full.pdf

If I had to tackle the problem myself and get something done quickly I would probably create a triangular grid (squares+diagonals), which is a planar graph for sure. Then to randomize it I would remove edges at random.

The disadvantage that method has over the one in the paper is that the graphs will tend to be very sparse.

EDIT: If after removing edges you end up with a node of degree 2 you can remove that node and replace it with an edge, making the graph less sparse aswell. Maybe you could generate some pretty good graphs by starting with a way too large grid and then removing edges and then removing degree 2 nodes a couple of times in a loop.