What is the most efficient way to generate a large (~ 300k vertices) random planar graph ("random" here means uniformly distributed)?
5 Answers
Without any other requirements, I'd say look up random maze generation. If you want cycles in the graph, remove some walls at random from a simple maze. The intersections in the maze become the nodes in your graph and the removed walls are the edges. That means you can select the number of nodes by choosing the size of the maze.
Mazes are typically done on a 2d grid with at most 4 connections from one point to another, but there is nothing stopping you from doing a maze on hex tiles, or something else.
Related