生成一个大型的随机平面图。
如何高效地生成一个大规模（约 300k 个顶点）的随机平面图（这里的“随机”是指均匀分布）？
如何检查一个图是否是平面图？
我正在学习C++中的平面图和着色相关知识，但我不知道如何安装算法来完成这项工作。请问有人能帮助我吗？ 以下是我的代码！然而其中仍有未完成的函数。如果有人知道“平面图”是什么，请修复下面的Planar_Graph函数！感谢您的帮助！：D 谢谢！：x # define MAX 100 int...
在二分图中减少交叉数量
我在绘制一个与此无关的图形时遇到了以下算法问题： 我们有一个平面双分图的图形，其中不相交的集合按列排列如图所示。 如何重新排列每列中的节点，以使边交错的数量最小化？ 我知道这个问题对于一般图是NP难题（链接），但考虑到图是双分图，是否有一些技巧可用？ 作为后续，如果有第三列w，它只连接...
在图中最小化交叉边
我正在使用networkx（一个Python图形绘制包）http://networkx.lanl.gov/index.html进行我的一个项目。虽然networkx非常酷，但由于交叉边的数量，其显示功能有些糟糕。是否有一种算法可以对节点进行排序，以便最小化交叉边？
平面图布局
在布局图形时，有哪些边重叠最小化技术？（最好与GraphViz相关）此外，是否存在可以以平面方式布局图形的现有软件？ 当前布局-http://www.evecakes.com/doodles/master.gif 左上角的粉色部分看起来不错，而浅蓝色部分则存在一些可避免的边重叠。
平面图中的小环查找
我有一个几何无向平面图，即每个节点都有一个位置，没有两条边相交，我想找到所有没有边相交的环。 这个问题是否已经有了好的解决方案？ 我计划做的是一种类似于A*的解决方案： 将每条边作为路径插入到最小堆中 使用每个选项扩展最短路径 剔除回到起点之外的路径（可能不需要） 剔除将成为第三条...
平面图（带嵌入）的实现方案
为了本文的目的，所谓的平面图，或者说平面地图，是指一种可以在平面上（或等价地在球面上）绘制的抽象图形，以及每个顶点处边缘的循环顺序，根据特定的绘制方式确定该附加信息决定了嵌入到球体上（移动顶点和边缘的方式使它们永远不会相交其他顶点/边缘）。我确实希望允许循环和多重边缘。 例如，假设我们按照以...
连接偶数个节点而不交叉
我有两组n个节点。现在我想将一组中的每个节点与另一组中的一个节点连接起来。所得到的图形应该没有交点。 我知道几种扫描线算法（Bentley-Ottmann-Algorithm）可以检查交点的位置，但我找不到一个解决这些交点的算法，除了暴力方法。 一组中的每个节点都可以连接到另一组中的任何其...
如何对平面嵌入进行认证？
我即将实现一个计算平面嵌入的算法。 我已经开始通过运行一组图表（罗马图表）并将结果与另一个实现（yfiles）的结果进行比较来验证我的结果。但是，因为对于给定的平面图可能存在许多不同的嵌入，所以我只能检查平面/非平面答案是否相等。 我如何验证我计算出的嵌入（邻接列表中的排序）是正确的平面嵌...
最快的图形平面化算法
我正在使用Processing开发一个用于处理复杂数据和流程的导航系统。作为其中的一部分，我深入研究了图形布局。布局算法方面，我的看法是：力导向算法太简单了（看看它的规模...哈哈），特征向量投影很酷，Sugiyama层次结构看起来不错，但在具有复杂图形的情况下会很快失败。虽然到目前为止我一直...