如何用不相交的边绘制图形？

Question

我有图的邻接矩阵.我需要在没有相交边缘的情况下对该图进行虚拟化.图中的顶点可以随机排列.我知道一个解决方案 - 交叉点的所有边的枚举.如果边相交,则重新排列顶点,但对于大量顶点(超过20个)来说它太昂贵了.如何检查相交边缘的任何其他想法？

Answer 1

在 3D 平面中可视化具有不相交边的任何图形确实很容易。

1) 将所有顶点放置在 3D 平面中的任意点上，使得没有三个顶点共线且没有四个顶点在同一平面上。

2）遍历邻接矩阵并绘制直线/曲线来连接顶点。

在 2D 平面中，不能保证解的存在。例如，考虑最坏的情况，有大约 10 个顶点，每个顶点都相互连接。