check_planarity

check_planarity(G, counterexample=False)

检查图是否是平面图，并返回反例或嵌入。

一个图是平面图当且仅当它可以被绘制在一个平面上，且没有任何边相交。

参数:

GNetworkX 图

counterexample布尔值

只有当设置为 True 时，才会返回库拉托夫斯基子图（用于证明非平面性）。

返回:

(is_planar, certificate)(布尔值, NetworkX 图) 元组

如果图是平面图，则 is_planar 为 True。如果图是平面图，certificate 是一个 PlanarEmbedding 实例；否则，它是一个库拉托夫斯基子图。

另请参阅

is_planar

检查平面性，但不创建 PlanarEmbedding 实例或反例。

说明

（组合）嵌入由每个顶点的关联边的循环顺序组成。给定这样的嵌入，文献中讨论了多种绘制图的方法（受各种约束，例如整数坐标），参见例如 [2]。

平面性检查算法和组合嵌入的提取基于 Left-Right Planarity Test [1]。

只有当相应参数被设置时，才会生成反例，因为反例生成的复杂度更高。

参考文献

[1]

Ulrik Brandes: The Left-Right Planarity Test 2009 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.217.9208

[2]

Takao Nishizeki, Md Saidur Rahman: Planar graph drawing Lecture Notes Series on Computing: Volume 12 2004

示例

>>> G = nx.Graph([(0, 1), (0, 2)])
>>> is_planar, P = nx.check_planarity(G)
>>> print(is_planar)
True

当 G 是平面图时，返回一个 PlanarEmbedding 实例

>>> P.get_data()
{0: [1, 2], 1: [0], 2: [0]}