生成大型随机平面图

Question

生成大型(~300k顶点)随机平面图的最有效方法是什么("随机"在这里意味着均匀分布)？

Answer 1

你看过玻尔兹曼采样吗？请参阅 Eric Fusy 的论文“线性时间内平面图的均匀随机采样”。这篇论文和实现可以在他的主页上找到，论文称可以在几秒钟内生成 100K 大小的实例。

Answer 2

另一种可能性在于随机选择坐标,然后计算Delaunay三角剖分,这是一个平面图(并且看起来也很漂亮).请参阅http://en.wikipedia.org/wiki/Delaunay_triangulation有O(n log(n))算法来计算这种三角测量.

Answer 3

一种方法是尝试生成一个随机图，它满足与平面图类似的约束（例如，边 <= 3*顶点 - 6），并使用 Tarjan 的平面测试算法在 O(n) 时间内检查它是否是平面的。如果不是平面，则再次生成。不过，不确定这对于 300K 顶点的效率有多高！（或者它是否会为您提供具有统一概率的图形）。

有一些关于生成平面图的文献，我可以在这里找到一篇论文：生成带标签的平面图，它显然期望 O(n^4) 运行时间，并且可能也不值得。也许那里的参考资料会帮助您找到可能有帮助的东西。

祝你好运！