Menu
What is the most efficient way to generate a large (~ 300k vertices) random planar graph ("random" here means uniformly distributed)?
617
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.
The equation v−e+f=2 v − e + f = 2 is called Euler's formula for planar graphs .
A planar graph is a graph that we can draw in a plane in such a way that no two edges of it cross each other except at a vertex to which they are incident.
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.
173
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
