问题标签 [planar-graph]

我即将实现一种计算平面嵌入的算法。

我已经开始通过运行一组图（罗马图）并将我的结果与另一个实现的结果（yfiles）进行比较来验证我的结果。但是，我只能检查平面/非平面答案是否相等，因为对于给定的平面图，可能存在许多不同的嵌入。

如何验证我计算的嵌入（在邻接列表中排序）是正确的平面嵌入？

我已经发现了一些我可能得到错误嵌入的情况。对于失败的图，通常手动绘制嵌入变得很困难。我发现boost 文档指出，给定任何图形，都可以生成图形的平面图，这将证明该图形是平面的，并且平面性证书很容易检查。但我也不确定是否/如何仅从有序的邻接列表中以一种万无一失的算法方式创建这样的绘图。

（顺便说一句。这是我的代码）

我有一个有向平面图。因此我可以进行平面嵌入。我必须节点 s 和 t 并且我想根据特定的嵌入找到 s 和 t 之间最左边的路径。

左定义为评论中描述的大卫。这意味着“左”是相对于无限面和顺时针/逆时针约定定义的。如果循环 p*rev(q) 相对于缠绕无限面而言至少与任何其他面一样逆时针，则路径 p 位于具有相同端点的路径 q 的左侧。

这怎么可能？我不知道如何告诉我的程序是否留下了另一条路径。我读了几篇论文，但他们没有解释如何实现它。有人有想法吗？

如果我有他的面孔列表，是否有绘制平面图的算法？

我知道有一些复杂的算法，例如路径加法和顶点加法，它们可以测试平面性并产生平面嵌入，但这不是我想要的。

Puzzle : Given an even number of points in general positions on the plane (that is, no three points co-linear), can you partition the points into pairs and connect the two points of each pair with a single straight line such that the straight lines do not overlap?

My Solution : One simple approach (that seems just too simple).

Start with the point with left-most x-coordinate and then draw a line to the next least left-most x-coordinate. Then find the next least pair of points and connect and so on!

Is this correct?

我现在正在学习Minimum-Spanning-Tree这个话题，我明白了大部分，但我还有一些我不明白的东西。我正在处理无向加权图。

首先，我知道找到 MST 的成本为 O(E*log V)。现在，当我们处理平面图时，我想将其优化为线性时间 - O(V+E)。

其次，我在单位正方形中看到了 n 个点的示例，并且我成功地证明了存在权重为 O(sqrt n) 的 MST。问题是我找不到找到这个 MST 的算法。

谢谢大家，或者

我正在寻找以下任务的算法：

我们正在玩以下游戏：在我们面前绘制了一个平面图，例如

我们可以看到边在 3 个地方相交。我们将在不删除任何边的情况下移动顶点，以使边不再相互交叉。例如，对于给定的图，我们可以通过以下两个步骤来完成，首先移动顶点 E，

然后通过移动顶点 B

这是一个非常简单的例子。给出的平面图可能要复杂得多。

必须转换为

任何人都可以通过反复试验来做到这一点，但是在给定任何平面图结构的情况下，需要遵循的一般算法是什么。

欢迎任何形式的提示或解决方案。提前致谢！:)

boost 图形库似乎具有为最大平面图实现的平面嵌入算法。它是否也有任何实现平面化非平面图的方法？希望能最大限度地减少过境点。

我发现Open Graph Drawing Framework有一些平面化代码，但如果存在，我宁愿在 boost 中使用一些东西。

这个前面的问题问了一些类似的问题，但不是直接关于在 boost 中是否存在这种算法。

我正在尝试编写一种算法来创建图的对偶。为了检查图形是否是平面的，我通过vtkBoostGraphAdapter. 这很好用（仅在vtkUndirectedGraph-s 上，但现在还可以）。(boost.org/doc/libs/1_56_0/libs/graph/doc/boyer_myrvold.html)

要创建对偶，我需要遍历平面图的面，为此我还有一个名为planar_face_traversal_visitor. (boost.org/doc/libs/1_56_0/libs/graph/doc/planar_face_traversal.html) 有一个人，Aaron Windsor，他实现了适当的访问者类，能够在 Boost 中创建图的对偶。（https://github.com/aaw/boost_planar_graph_dual）仅使用 Boost 也可以正常工作，但我也想使用vtkBoostGraphAdapter.

这是我的代码： http: //pastebin.com/g0Mtw6Ph

这些是我的错误：

• /usr/local/boost_1_56_0/boost/property_map/property_map.hpp :302:19: 'const boost::iterator_property_map, std::__1::allocator > > *>, boost::vtkGraphIndexMap 类型没有可行的重载运算符 [ ] , std::__1::map, std::__1::allocator > >, std::__1::map, std::__1::allocator > > &>'
• /usr/local/boost_1_56_0/boost/property_map/property_map.hpp :309:5: 'const boost::iterator_property_map, std::__1::allocator > > *>, boost::vtkGraphIndexMap 类型没有可行的重载运算符 [ ] , std::__1::map, std::__1::allocator > >, std::__1::map, std::__1::allocator > > &>'
• /usr/local/boost_1_56_0/boost/property_map/property_map.hpp :302:19: 'const boost::iterator_property_map, std::__1::allocator > *>, boost::vtkGraphIndexMap, 类型没有可行的重载运算符 [] ， std::__1::set, std::__1::allocator >, std::__1::set, std::__1::allocator > &>'
• /usr/local/boost_1_56_0/boost/property_map/property_map.hpp :309:5: 'const boost::iterator_property_map、std::__1::allocator > *>、boost::vtkGraphIndexMap 、 std::__1::set, std::__1::allocator >, std::__1::set, std::__1::allocator > &>'
• /usr/local/boost_1_56_0/boost/plane_dual.hpp :38:38: 'edge_to_face_map_t' 类型（又名'iterator_property_map'）没有可行的重载运算符[ ]

在过去的几天里，我一直在处理这个问题，非常深入地阅读了源代码并尝试了一些事情，但我无法真正弄清楚问题所在。vtkBoostGraphAdapter是否为这种用法做好了适当的准备？

任何形式的帮助表示赞赏！

提前致谢！

西拉德

我只是在概念上想知道如何检查图形是否是外平面的。我知道您可以使用 BOOST 检查图形中的平面性，如何检查外平面性？提示？

我正在使用 Python 中的 NetworkX Graphs，我想找到我拥有的任何给定图的 Kuratowski 子图。

Boyer-Myrvold 平面图测试算法可以返回一个现有的 Kuratowski 子图，如果该图不是平面的（顶点数 n 为 O(n)），所以我希望可能已经有该算法的实现或Python中的类似算法。到目前为止，我一直找不到一个，而且我有点不愿意从原始研究论文中重新实现它。

如果它可以轻松地与 NetworkX 库进行图形交互，那就更好了。