平面图检查器 — 测试一个图是否可以在不交叉的情况下绘制
我们的平面图检查器测试一个图是否有可能在平面上绘制而不出现边交叉，应用必要的边数条件（E ≤ 3V − 6，对二部图收紧为E ≤ 2V − 4），并且对于8个或更少顶点的图，显式搜索K₅或K₃,₃子图——两者中任意一个都能根据库拉托夫斯基定理确定性地证明非平面性。
快速解答
将图输入为边列表，检查必要的边数条件并搜索被禁止的K₅/K₃,₃子图——这是一种有力但并非完全穷尽的平面性检验。
输入边，格式为节点A-节点B，例如A-B, A-C, A-D, B-C, B-D, C-D。
如何使用 平面图检查器 — 在线库拉托夫斯基式检验
- 1
将图输入为逗号分隔的边列表，例如A-B, A-C, A-D, B-C, B-D, C-D。
- 2
点击'计算'检查必要条件并搜索被禁止的子图。
- 3
查看判定结果——'确定非平面'或'可能为平面（不确定）'——以及推理步骤。
为什么使用 平面图检查器 — 在线库拉托夫斯基式检验？
如果一个图可以在平面上绘制而没有任何两条边交叉，则该图是平面图。库拉托夫斯基定理给出了一个精确的刻画：一个图是非平面的，当且仅当它包含K₅（5个顶点的完全图）或K₃,₃（两组各3个顶点的完全二部图）的细分。完全检测这些图的细分或子式需要复杂的算法（如Boyer-Myrvold），远超客户端计算器所能即时执行的范围——因此本工具转而采用了范围透明的方法：始终检查必要的边数上界（一种快速、精确地排除许多非平面图的方法），并且对于小图（8个或更少顶点），额外直接搜索作为字面子图出现的K₅或K₃,₃。找到其中任意一个都能确定性地证明非平面性；未找到则是平面性的有力提示，但不是完整证明，因为它无法捕捉这些禁止图的细分（边扩展）副本。