问题标签 [planar-graph]

给定一个具有顶点权重 W(V) 的无向循环平面图 G(V,E)、一个嵌入 E(G) 和两个节点 s 和 t 的固定平面，我需要找到 G 的一个分区，将其划分为两个连通分量S(G) 和 T(G)，其中 s 在 S(G) 中，t 在 T(G) 中。顶点 s 和 t 都属于嵌入 E(G) 中的外部面。

我希望分区能够很好地平衡 - 它们应该具有几乎相等的顶点权重之和。

请问有什么好的算法的想法吗？

我正在为我的一个项目使用networkx（一个python图形绘图包）http://networkx.lanl.gov/index.html。虽然 networkx 很酷，但由于交叉边缘的数量，显示功能有点糟糕。有没有办法最小化图中的交叉边？我的意思是一种算法，它可以以最小化交叉边缘的方式对节点进行排序？

我有一个仅由星图组成的图G。星形图由一个中心节点组成，该中心节点与其中的每个其他节点都有边。令H ₁ , H ₂ ,…,H _n是G中存在的不同大小的不同星图。我们将所有节点的集合称为任何星图中的中心R。

现在假设这些星图正在构建其他星图的边，使得R中的任何节点之间都没有边。那么，如果图形应该保持平面，则在R中的节点和不在 R 中的节点之间最多存在多少条边？

我想要这样的边缘数量的上限。我想到的一个上限是：将它们视为二分平面图，其中R是一组顶点，其余顶点形成另一组A。我们对这些集合（R和A）之间的边感兴趣。由于它是平面二分的，因此此类边的数量以G中节点数量的两倍为界。

我觉得有一个更好的界限，可能是A中节点数的两倍加上R中的节点数。

如果你能反驳我的直觉，那也很好。希望你们中的一些人可以提出一个很好的界限以及一些相关的论点。

我有一个家庭任务：

为了使平面图嵌入的可视化器（或铺设我不知道这个过程的正确词）。

平面图与平面图同构，平面图是在平面上绘制的图，其边不相交。

我需要一个算法来做到这一点，有一篇俄语文章，那里描述了名为“Gamma 算法”的算法，但我想找到更多信息，我什至找不到关于“Gamma 算法”的任何信息（在英文，好像还有别的名字），也没有关于英文的其他算法。

任何人都可以建议算法的名称及其描述的链接吗？

ps 对不起，如果我的英语不好:)

我想在 2D 空间中生成随机点，这些点将是平面图的节点（使用Gabriel 图算法或 RNG 构建）。

我编写了java代码来做到这一点，但我有两个难题要解决。

1）我需要图的所有边不超过给定的阈值

2）在我想知道图形的面之后，面是由边连接的节点的集合。一个面不包含其他节点。在下图中，面部由标签（F1，F2 ...）签名

这两件事怎么做？一些算法？有一些方法已经知道吗？

下面是我必须创建的图表示例

http://imageshack.us/photo/my-images/688/immagineps.png/

我遇到了许多可以表述为图形问题的问题。它通常是 NP 难的，但有时可以证明该图是平面的。因此，我对学习这些问题和算法很感兴趣。

据我所知：

1. 平面图中的最大切割
2. 平面图中的四色
3. 三次平面图中的最大独立集

希望有人能完成这份清单。

我正在用 Java 开发一个小项目，如下所述：

输入：有向图的对象列表。（具有不同类型边的节点：继承、内部类、朋友类等） 输出：类图，尽可能平面。

我的问题是：我想要一些第三方软件来为我做这件事，或者至少有一个选择节点和边的算法，以使我的图形尽可能保持平面。

编辑：我看到我可能没有清楚地写出我想要的东西......我不想生成基于 Java 项目及其文件的类图，但我正在解析 C++ 文件并从上面输入中描述的列表中获取。然后我想调用该列表上的一些函数并获取我的图表。我试图使用 JGraph 或 JGraphT，但不幸的是我没有找到任何适合我要求的图论功能。

问候，丹尼尔

我正在使用 Processing 为复杂的数据和流程开发导航系统。作为其中的一部分，我已经深入了解了图形布局。这一切都很有趣，我对布局算法的看法是：力导向适用于娘娘腔（看看它的比例......哈哈），特征向量投影很酷，Sugiyama 层看起来不错，但在图形图上很快失败，虽然我依赖到目前为止，在特征向量上，我需要最小化边缘交叉以真正到达数据点。我知道，我知道 NP-complete 等。

我应该补充一点，我在应用xy拳击和使用类似 Sugiyama 的排列来减少跨行和列的边缘交叉方面取得了一些成功。即：图形 (|V|=90,avg degree log|V|) 可以从 11000 个交叉点 -> 1500（按盒装特征向量）-> 300 通过交替行和列排列来减少交叉点。

但是局部最小值……无论它是什么都围绕着这个标记，结果并不像它可能的那样清楚。我对 lit 的研究表明，我真的很想使用平面化算法，就像他们在 VLSI 中使用的那样：

1. 使用 BFS 或其他东西来制作最大平面子图 1.a。布局平面子图 nice-like
2. 巧妙地添加突出边来恢复原始图

请回复您对最快平面化算法的想法，欢迎您深入了解您熟悉的任何特定优化。

非常感谢！

所以我最近一直在阅读一些关于图论和结理论关系的论文，这让我想到了在代码中表示结。

我目前对这个问题的直觉是将结视为本质上的平面图，其中每个顶点位于任何交叉点。然后，我们还将存储任何给定顶点的交叉点是如何定向的。

这几乎是如何完成的，还是有更好的方法？

谢谢！

问：为什么凸多边形被认为是设计图形算法的更好选择？

我的 A. 凸多边形是平面的，更容易剪裁。

我的回答有点简短，我不确定我的回答是否正确，请问其他人可以扩展或给我一个更好的答案吗？