check_planarity

check_planarity(G, counterexample=False)

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

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

Parameters:

GNetworkX图

counterexamplebool

仅当设置为true时，才会返回一个Kuratowski子图（用于证明非平面性）。

Returns:

(is_planar, certificate)(bool, NetworkX图) 元组

is_planar为true表示图是平面图。 如果图是平面图， certificate 是一个PlanarEmbedding； 否则，它是一个Kuratowski子图。

See also

is_planar

不创建 PlanarEmbedding 或反例的情况下检查平面性。

Notes

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

平面性检查算法和组合嵌入的提取基于左-右平面性测试[1]。

仅当相应参数设置时才会生成反例，因为反例生成的复杂性较高。

References

[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

Examples

>>> 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]}