Generate a large random planar graph

问题:

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

回答1:

Another possibility consists in randomly choosing coordinates and then compute a Delaunay Triangulation, which is a planar graph (and looks nice as well). See http://en.wikipedia.org/wiki/Delaunay_triangulation There are O(n log(n)) algorithms to compute such a triangulation.

回答2:

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.

回答3:

Have you looked at Boltzmann sampling? See the paper by Eric Fusy "Uniform random sampling of planar graphs in linear time". The paper and the implementation are available in his homepage which the paper says can generate instances of size 100K in a few seconds.

回答4:

If by uniform you mean uniformly distributed in space, then this is a pretty fast algorithm I developed for generating planar graphs for a spatial ecological/evolutionary simulator. It will generate random planar graphs with an expected degree you specify, of course with some variation around it. You could extend it to pick the expected degree based on a uniform random number if instead you wanted uniform random degrees in your planar graph.

https://github.com/briandconnelly/seeds/blob/master/seeds/plugins/topology/CartesianTopology.py

回答5:

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!