python - 用于 Boyer-Myrvold 平面性测试或 Kuratowski 子图识别的 Python 库

Question

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

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

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

Answer 1

John Boyer 的部分平面代码 ( https://code.google.com/p/planarity/ )有一个 Python 包装器，这可能是您正在寻找的。它位于https://github.com/hagberg/planarity。

它有一个 NetworkX 接口，允许您测试平面性并找到 Kurotowski 子图（如果不是）。例如

https://github.com/hagberg/planarity/blob/master/examples/networkx_interface.py

import planarity
import networkx as nx
# Example of the complete graph of 5 nodes, K5
G=nx.complete_graph(5)
# K5 is not planar
print(planarity.is_planar(G)) # False
# find forbidden Kuratowski subgraph
K=planarity.kuratowski_subgraph(G)
print(K.edges()) # K5 edges