graph-theory - 绘制平面图的算法

Question

如果我有他的面孔列表，是否有绘制平面图的算法？

我知道有一些复杂的算法，例如路径加法和顶点加法，它们可以测试平面性并产生平面嵌入，但这不是我想要的。

Answer 1

有许多可视化图表的技术，整个教科书都专门讨论这个主题。如果您正在寻找一种快速的算法来实现，我建议您查看force-directed graph drawing。

这个想法是考虑顶点自然地相互排斥，但边将它们拉在一起。两种力（排斥力和吸引力）都应该是顶点之间距离的函数，并且直接作用于（或远离）相关顶点。像 (1/r^2) 表示排斥力和 ln(r) 表示吸引力的大小是好的。还要考虑在边界处施加的一些排斥力，以阻止单独的连接组件飞向无穷大。

该算法类似于：

1. 将所有顶点放置在平面上的随机点上。

2. 计算作用在每个顶点上的净力。

3. 将每个顶点移动一小部分净力。

4. 如果没有顶点移动超过某个容差值，则绘制图形，否则转到 2。

如果需要动画，可以将步骤 4 替换为“绘制图形，然后转到 2”。

它并不快，也不能保证平面表示，但它很容易实现，并且通常可以很好地捕捉平面性。高度连接的顶点最终彼此靠近。