+ 2

How to generate large random planar graphs?

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?

8th Dec 2018, 11:44 AM
Julian Fechner
Julian Fechner - avatar
1 Odpowiedź
+ 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.
8th Dec 2018, 3:02 PM
Schindlabua
Schindlabua - avatar