Hen*_*nri 3 algorithm graph-theory graph planar-graph
我有一个固定节点位置的无向图.无法移动,合并,删除或以其他方式更改节点.边缘固定在它们的节点上,但不必是直的.
我需要知道是否可以"弯曲"或"绘制"边缘,使得图形是平面的(即没有边缘交叉).
如果存在这样的算法或实现,或者您只是想知道如何操作,请告诉我!
这个问题的答案是"J. Pach和R. Wenger.将平面图嵌入固定的顶点位置.图表组合,17:717-728,2001"如下:
n个顶点上的每个平面图都允许平面嵌入,其将每个顶点映射到预先指定的不同位置,并且每个边缘到具有O(n)个弯曲的多边形曲线.
这种嵌入可以在O(n ^ 2)时间内构建.
所以答案是,当且仅当图形是平面时,才能构造这样的图形.根据维基百科,您可以在O(n)时间内测试图形是否为平面.