gpt4 book ai didi

algorithm - 具有固定节点位置的图形平面度

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:09:01 28 4
gpt4 key购买 nike

我有一个具有固定节点位置的无向图。不能移动、合并、删除或以其他方式更改节点。边固定在它们的节点上,但不必是直的。

我需要知道是否可以“弯曲”或“绘制”边以使图形成为平面(即没有边交叉)。

如果存在这样的算法或实现,或者您只是知道如何去做,请告诉我!

最佳答案

"J. Pach and R. Wenger. Embedding planar graphs at fixed vertex locations.Graphs Combin., 17:717–728, 2001" 回答了这个问题作为:

Every planar graph on n vertices admits a planar embedding which maps each vertex to a prespecified distinct location and each edge to a polygonal curve with O(n) bends.
Such an embedding can be constructed in O(n^2) time.

所以答案是当且仅当图是平面的时,您可以构造这样的图。您可以根据 wikipedia 在 O(n) 时间内测试图形是否是平面的.

关于algorithm - 具有固定节点位置的图形平面度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37436873/

28 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com