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