check_planarity

check_planarity(G, counterexample=False)

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

图是平面的，如果它可以在一个没有任何边交点的平面上绘制。

参数

G网络X图表

counterexample布尔尔

只有设置为TRUE时，才会返回Kuratowski子图(用于证明非平面性)。

返回

(is_planar, certificate)(Bool，NetworkX图)元组

如果图形是平面的，则IS_PLANET为真。如果图形是平面的 certificate 是PlanarEmbedding，否则是Kuratowski子图。

笔记

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

组合嵌入的平面度检验算法和提取基于左右平面度检验 [1] .

只有在设置了相应的参数时才会生成counterexample，因为counterexample生成的复杂性更高。

工具书类

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，医学博士Saidur Rahman：平面图绘制讲义计算系列：2004年第12卷