查找与 k5 或 k3,3 同态的子图

Question

给定一个简单图，问题是检查是否存在与 k5 或 k3,3 同构的子图，如果存在，则输出存在的子图（k5 或 k3,3 或两者）。我需要一种相当快的算法，可以在几分钟内处理具有 15 个顶点的图。我知道我可以检查这 2 个图之一是否包含在 Tarjan 的图平面性算法中，但我也想知道它是哪一个。

我正在用 C++ 进行编码，我拥有的最佳解决方案是获取边缘的所有子集，但这非常昂贵。另一方面，在我的第一次尝试中，我修复了顶点，但是我无法检查子图是否与 k5 或 k3,3 同胚。我尝试删除 2 度顶点并连接邻居，但仍然有一些边缘应该被忽略，而且我没有找到有效删除它们的方法。

Answer 1

也许 SageMath 可以做点什么。它有 Boyer (C) 平面算法的包装。以下是一个例子。

sage: G = graphs.SchlaefliGraph()
sage: G.is_planar()
sage: %time s=G.is_planar(kuratowski=True)
sage: s[1]