问题标签 [planar-graph]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
algorithm - 平面图中的小循环查找
我有一个几何无向平面图，即每个节点都有一个位置并且没有两条边交叉的图，我想找到所有没有边交叉的循环。
这个问题有什么好的解决方案吗？
我打算做的是一种A*类似的解决方案：
- 将最小堆中的每条边作为路径插入
- 使用每个选项扩展最短路径
- 剔除循环回到起点以外的路径（可能不需要）
- 剔除将是第三个使用给定边缘的路径
有没有人看到这个问题？它甚至会起作用吗？
c++ - 如何检查图是否为平面图？
我正在学习 C++ 中的平面图和着色。但我不知道安装算法来完成这项工作。有人请帮助我吗？
这里我有一些信息给你！这是我的代码！而且它还有一个功能没有完成。如果有人知道什么是“平面图”，请修复下面的 Planar_Graph 函数！:D 非常感谢！：X
输入文件示例：
linux - 支持平面图测试的开源图形绘图程序？
在图论中，平面图是可以嵌入到平面中的图，也就是说，它可以在平面上以这样一种方式绘制，即它的边只在端点处相交。
它们有许多用于平面图测试的算法（即确定给定图是否为平面图）。最好的在 O(n) 中，其中 n 是顶点数。
存在哪些支持以下功能的开源程序：
- 可以绘制平面图
- 支持 O(n) 平面图测试。
- 支持可变节点大小。
- 支持固定绘图边界区域
- 是否开源
algorithm - 平面图布局
布置图时有哪些边缘重叠最小化技术？（最好与 GraphViz 相关）还有任何现有的软件可以以平面方式布局图形吗？
当前布局 - http://www.evecakes.com/doodles/master.gif
左上角的粉色部分看起来不错，而浅蓝色部分有一些可避免的边缘重叠。
hamiltonian-cycle - 在三次平面图中寻找哈密顿循环
我有相对较小的（40-80 个节点）三次（3 正则）平面图，我必须确定它们的哈密顿性。我知道这个任务是 NP 完全的，但我希望渐近指数时间算法对于我感兴趣的图形大小来说仍然非常快。
algorithm - 生成一个大的随机平面图
生成大型（约 300k 个顶点）随机平面图（这里的“随机”表示均匀分布）的最有效方法是什么？
graph - 非平面图的平面化算法
是否存在用于平面化非平面图的流行算法。
我目前正计划在 Boost ( Boost Graph Library ) 中为无向图实现正交平面布局算法。BGL 有一个实现来检查无向图的平面性（Boyer-Myrvold Planarity Testing），我计划使用此方法返回的平面嵌入来进行正交布局。
但是我不确定如果输入图是非平面的应该怎么做。我是否应该对在这种情况下返回的 Kuratowski 子图做一些事情以使图平面化。
Google 搜索“非平面图的平面化”会返回多篇研究论文。我不知道从哪里开始。
c# - C# 中的平面嵌入（Planar Face Traversal）算法
我有一个图表G。该图是平面图。
我希望找到图表的所有面。我知道构建平面嵌入是找到面（或区域或循环）的方法，这样所有边必须最多由 2 个面共享。
在 C# 中是否有现成的平面嵌入算法实现？商业或开源都可以。
graph - n节点平面图中m循环存在的复杂度
G 是具有 n 个节点的平面图。
以下问题的复杂性是什么？
- A: G 是否包含 m 循环？(m-cycle是一个简单的循环，有m个节点，m
- B：计算 G 中所有 m 循环的复杂度。
- 如果 G 是任意给定图，A 和 B 的复杂度是多少？
指向书籍和论文也很有用...
algorithm - 图结构的直线平面嵌入
这是我的问题：我有一个图形结构（带有直线边），我知道它是平面的（即存在没有边交叉的图形嵌入）。我需要一种算法来获取我的图形并生成它的直线平面嵌入。该算法不需要太高效（O(N^2) 算法就可以了）。有什么想法/建议吗？