问题标签 [planar-graph]

我有许多多边形，每个多边形都表示为一个点列表。我正在寻找一种快速算法来遍历多边形列表并取消所有交叉边，直到没有交叉边为止。

当前版本的伪代码：

这可以通过用递归替换 while 循环来改进。但是，它在性能方面仍然很差。

下面是解开*的简单示例。实际上会有大量的多边形和每个多边形的相当数量的点（大约 10-500）。红线显示哪些两条边未被交叉。结果应该始终是一系列平面图，尽管不确定是否有多个有效结果或只有一个。

编辑：这次我先添加线条，然后添加点，并使用更复杂的形状。假装点是固定的。

我正在尝试为平面图生成构建一些算法。我已经阅读了很多关于这个主题的材料，这里有一些结果：

在这里，我写了一些构建平面图的函数......

当我启动我的程序时，它会以这种方式生成许多平面图：

所有这些代码都有效，但我发现在测试图形（级别）24、36、...时不是平面的。

我知道欧拉公式，所以我尝试通过欧拉公式生成我的顶点/边，但正如我所见，它并没有真正起作用。

我正在尝试创建一个在点之间具有尽可能多的直边的图形，而不允许任何边在 Java 中相交。基本上，我正在尝试制作一个带有随机点数的平面图。当给定一个已经有边的图时，我有点理解如何检测平面图，但我对如何从随机节点实际创建平面图感到困惑。想到的唯一方法是随机创建图表然后测试它们，但这似乎非常低效。

谢谢

我创建了一个在顶点之间添加边的程序。目标是在不交叉的情况下添加尽可能多的边（即平面图）。复杂性是什么？

尝试：由于我使用深度优先搜索，我认为它是 O(n+m)，其中 n 是节点，m 是边缘。

此外，如果我们将边数绘制为 n 的函数，它会是什么样子？

（*我重新发布这个问题，因为上次没有人回答*）

就本文而言，平面图或平面图是指可以在平面上（或等效地在球体上）绘制的抽象图，以及每个顶点的边的圆形顺序到特定的此类绘图。这个额外的信息决定了球体上的嵌入（直到移动顶点和边，使其永远不会与任何其他顶点/边相交）。我确实想允许循环和多个边缘。

例如，假设我们已经构建了如下图。在平面中绘制两个顶点（A 和 B），以及连接这两个顶点的两条边。两条边共同形成一条简单的闭合曲线 γ。现在再添加两个顶点，A' 和 B'，并将 A 和 A' 与一条边连接，同时将 B 和 B' 连接起来。

这个抽象图将有两个不等价的嵌入，根据顶点 A' 和 B' 是否被曲线 \gamma 分开。

我的问题是：有没有实现这种平面图的 Python 包？

我对一个可以创建平面图绘图（当然是关于嵌入）以及执行一些标准操作（例如，给出面数，形成对偶图等）的包感兴趣

如果 Python 中不存在这样的包，我也会对其他语言的实现感兴趣。

当然，有各种包可以实现图形的绘制和图形理论算法。但是，我没有注意到在任何这些中使用已经带有嵌入的图形的可能性。参考将不胜感激。

编辑。让我进一步详细说明。如果球体与自身的同胚相关，则同一图在球体中的两个嵌入是等价的。如上所述，平面图的嵌入通常不是唯一的，所以我所要求的与测试图形的平面性并绘制一些嵌入不同。

有几种组合方式可以对嵌入进行编码，直到达到这个等价。可能最简单的方法是记录每个顶点的边的循环顺序（“旋转系统”），但还有很多其他的。有关讨论和参考，请参阅Wikipedia 上有关图嵌入的文章。

人们可能希望对这种组合嵌入执行一些明显的操作，例如找到图形的面，找到边/顶点相邻的面，在面中插入顶点，细分边，绘制图片嵌入等

是否有一种或几种表示 Python 中可用的组合图嵌入的数据结构的实现？（我注意到图嵌入在一般表面上是有意义的，尽管我主要对球体的情况感兴趣。）

我有一个特定类型的平面图，我发现搜索一种可以合法地为其顶点着色的算法很有趣。关于这种类型的图表，它非常简单和酷：

考虑任何具有n>2个顶点和k个叶子的树T。让我们将G(T)表示为由T构造的图，该图通过将其叶连接到k -cycle 以使G(T)是平面的方式。

我想出的问题是用3种颜色为G(T)着色。显然，作为平面图的G(T)是4可着色的，但我认为（没有证据）由于其简单性，它几乎总是3可着色的。几乎总是意味着只有当T是一颗星星并且只有奇数个叶子时，G(T)才是4可着色的。

我正在寻找一些算法，或者也许可以证明我的假设可以很容易地转化为算法。我将非常感谢任何帮助和提示。

如果我不够清楚，我会举一个例子：

令 T 为一棵树，其边 E(T) = { {1,2}, {2,3}, {2,4}, {4,5} } 然后 E(G(T)) =集合：E(T) 和 { {1,5}, {5,3}, {3,1} }，因为我们将叶子 1,5,3 连接成一个循环。

我有一组不相交的线，其中一些在顶点处连接。我试图找到包含给定点的最小多边形（如果存在）。所以，在下图中，在所有线段的列表中，给定红色的点，我只想得到蓝色的点。我正在使用 Python，但可能会采用其他语言的算法；我不知道这个问题叫什么。

我有一个通用平面图的组合嵌入（顶点、边、顶点周围边的循环排序和外部面），我需要绘制它。

顶点必须是无维的，并且绘图必须符合定义的围绕顶点（以及外部面）的边的循环排序，即使输入图不是 3 连通图或最大平面图。

如果绘图算法已经实现（可能在 Java 库中）会更好，但是有算法解释的论文仍然足够。

在为不相关的事物绘制图表时，我遇到了以下算法问题：

我们有一个二分图的平面图，不相交的集合按列排列，如图所示。我们如何重新排列每列中的节点，以使边缘交叉的数量最小化？我知道这个问题对于一般图（链接）来说是 NP-hard，但是考虑到图是二分的，有什么技巧吗？

作为后续，如果有第三列w，它只有边缘到v怎么办？还是更进一步？

我想知道有一些算法可以将图形变成平面图吗？我在谷歌搜索我没有找到可以帮助我的东西