Generate a large random planar graph

algorithm language-agnostic random graph-theory planar-graph
viaclectic picture viaclectic · Jul 12, 2010 · Viewed 9.8k times · Source

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

Answer

Ivo Blöchliger picture Ivo Blöchliger · Jan 15, 2013

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.

Related questions

Picking a random element from a set

How do I pick a random element from a set? I'm particularly interested in picking a random element from a HashSet or a LinkedHashSet, in Java. Solutions for other languages are also welcome.

Read More
Converting a Uniform Distribution to a Normal Distribution

How can I convert a uniform distribution (as most random number generators produce, e.g. between 0.0 and 1.0) into a normal distribution? What if I want a mean and standard deviation of my choosing?

Read More
Unique (non-repeating) random numbers in O(1)?

I'd like to generate unique random numbers between 0 and 1000 that never repeat (i.e. 6 doesn't show up twice), but that doesn't resort to something like an O(N) search of previous values to do it. Is this possible?

Read More