使简单图成为平面图的算法

Question

我想知道是否有一些算法可以将图形转换为平面图？我在谷歌上搜索了一下，但没有找到有用的信息。

- HinoHara

---

“Making” it planar指的是将其变成平面的意思。 - NPE

我更新了我的问题，请看图片。 - HinoHara

谷歌“图形可视化”。 - NPE

你要找的是一个平面图的嵌入。当一个图在平面上画出来时，不会有边交叉，则该图为平面图。有检查平面性的算法。而一旦确认它是平面图，就有线性时间算法来找到这样的绘画（称为平面嵌入）。请重新措辞您的问题，以便人们可以提供答案。 :) - Cyriac Antony

Answer 1

存在一种适用于每个平面图的欧拉定理。

定义: 平面图是一种可以在平面上绘制的图，使得边不相交。任何平面图将平面划分为称为图的面的数量的不相交区域。

欧拉定理：V-E+F=2 其中:

1. – V是顶点数，
2. – E 是边数，
3. – F 是面的数量

但是，我无法提供Java解决方案，因为不清楚您希望如何实现它。例如，如果要将图形转换为平面图，则可能需要画布和元素重新排列，这种实现将有些复杂。总体上，应以算法为导向，首先使用伪代码创建解决方案。

例如，我们有适用于每个平面图的欧拉定理，您需要找到一种方法将此定理应用于现有的非平面图形，然后进行测试。

步骤：（可能需要一些坐标）

• 确定顶点
• 确定边缘
• 确定面
• 找到一种计算顶点的方法
• 找到一种计算边数的方法
• 找到一种计算面数的方法
• 在画布上重新排列所有这些内容
• 测试定理，如果适用，则图形为平面图，否则，请再次重新排列。
• 请注意，通过使用坐标，您可以从一开始就确定图形是否可以绘制为平面图，但是在绘制时不应允许任何线边相交。

- nmargaritis

---

谢谢您的帮助，但我不知道如何重新排列顶点，如果您看一下图片，您就能理解问题，是的，我必须使用Java编写算法。 - HinoHara

欢迎，如果您的程序像图片所示一样工作，则它可以正常运行，因为两个图形都是平面图。它们的外观不影响规则，请查看此说明：!(https://thecafe.me/image/1/Nicholas_uOpsc.jpg)。 - nmargaritis

谢谢你的图片，我现在明白了你的解释。关于代码，我很快会更新我的问题，但是我的代码生成的图不是平面图，这是图片中的错误，我很抱歉。 - HinoHara

我认为你不能使用欧拉公式来确定一个图是否是平面的，因为你唯一能计算出面的方法是先制作一个平面表示。你需要编写库拉托夫斯基定理的代码，参见http://en.wikipedia.org/wiki/Kuratowski%27s_theorem，以确定图是否是平面的（即问题是否可解）。朴素的暴力算法很容易但效率极低。我怀疑高中作业不需要这种编码/算法知识。正如我在我的答案中所说，我不清楚实际问题是什么。 - Peter Webb

如果您知道如何确定什么是什么并证明可以以平面方式绘制图形，则可以使用欧拉公式。关于解决它的天真方法，应该是随机的，直到生成可以存储并在此之后直接到达结果的情况。例如，如果您发现一次如何绘制具有4个顶点，6条边和4个面的图形，则只需将其存储即可。因为它适用于所有具有类似特征的图形。 - nmargaritis

从实现的角度来看，有一个有用的东西：您需要使用坐标来确定什么是什么。例如，您需要计算的面始终是由3个顶点组成的三角形，否则它不是一个面（在最后的外部一般情况下+1）。 - nmargaritis

Answer 2

这篇评论太长了。所以请原谅我提供一个答案。

您的问题对我来说不是很清楚。图是否为平面图取决于该图本身，而不是它的绘制方式。 "在图论中，平面图是指可以嵌入平面中的图形，即可以以这样的方式在平面上绘制它，使其边仅在其端点处相交。"（从http://en.wikipedia.org/wiki/Planar_graph）。

您需要确定/检查图是否为平面图吗？

您需要以平面形式绘制它吗？

在您提供的示例中，为什么第二个图比第一个图更正确？仅仅因为没有相交的边吗？

假设您需要将此操作应用于其他图形，那么用于确定某些表示比其他表示更好的规则是什么？您的图示如何推广到其他图形？

您为什么要这样做？这有什么意义？如果这是作业，那么问题陈述是什么？如果这是现实生活中的情况，也许解释一下您真正要做什么会有所帮助。

- Peter Webb

---

非常抱歉，我知道我的解释不太好（我的英语很糟糕，但我能理解答案），例如我给出的第一个例子是错误的，你可以看一下更新！我想画一个简单的图（使用邻接矩阵）并将其转换为平面图（边仅在其端点处相交），这不是作业，而是学校的一个完整项目。再次对我的糟糕解释表示抱歉，非常感谢您的回答。 - HinoHara

请发布项目的要求。（希望翻译成英语）。其中一些部分很难。判断一个图是否是平面图很难。（我认为你不能简单地使用欧拉公式，因为在计算出面数之前，你必须已经有一个平面表示）。当绘制任意图形时，“使其看起来漂亮”也很困难。总体问题比我预期的高中项目要难得多。他们到底要你做什么？ - Peter Webb

我不在高中，这是我必须做的：我的程序必须以边仅在其端点相交的方式绘制平面图。使用随机邻接矩阵编码，使用Java AWT和Swing。 - HinoHara

所以他们给你一个邻接矩阵，保证它代表了一个平面图，然后你需要提供一个平面表示？http://cs.brown.edu/~rt/gdhandbook/chapters/straightline.pdf 描述了一些算法来完成这个任务。或者直接在谷歌上搜索“图的平面表示算法”。所有这些算法都比我想象中的高中作业要复杂得多。难道你不能选择其他项目吗？ - Peter Webb

非常感谢您的回答，是的，该程序使用一些算法将邻接矩阵转换为平面图，但我无法更改项目 :x - HinoHara

@PeterWebb 检查一个图是否是平面图并不难。它可以在多项式时间内完成。我感谢您为帮助 OP 所做的努力。 - Cyriac Antony