3

我用 Graphviz 画了一个小的平面图，但在一个地方有两条边的交点。我在 SO 上读到，并非所有平面图都可以在没有交点的情况下绘制，因为这是一个 NP 难题。我还读到 Graphviz 中甚至没有实现复杂的算法来做到这一点。但是那个交叉点很容易修复，所以可能有办法摆脱它。

以下是我使用的选项：

overlap = false;
splines = curved;
nodesep = 0.5;

这是图表： 平面图

那么，有没有一种方法可以修复一个交叉点（25-38 和 7-18）而不像我在这里所做的那样改变边缘的顺序？至少没有O(n^2)算法可以交换两个顶点并检查交叉点是否消失？

4

1 回答 1

2

这是一种修补程序：

在节点 7 和 25 之间添加一条不可见边，即7 -- 25 [style="invis"];。该子句可以添加到图形定义的末尾，因此它不应干扰任何自动生成。

感觉就像在作弊，但是，至少图形定义文件中有效负载边的顺序保持不变。

不幸的是，我无法解释为什么会这样。特别是，在其他节点之间添加与违规边相关的边不会产生所需的结果。

Graphviz 版本：2.38.0 (20140413.2041)

于 2018-02-02T14:59:53.900 回答