check_planarity#

check_planarity(G, counterexample=False)[source]#

Check if a graph is planar and return a counterexample or an embedding.

A graph is planar iff it can be drawn in a plane without any edge intersections.

Parameters:

GNetworkX graph
counterexamplebool: A Kuratowski subgraph (to proof non planarity) is only returned if set to true.

Returns:

(is_planar, certificate)(bool, NetworkX graph) tuple: is_planar is true if the graph is planar. If the graph is planar certificate is a PlanarEmbedding otherwise it is a Kuratowski subgraph.

See also

is_planar: Check for planarity without creating a PlanarEmbedding or counterexample.

Notes

A (combinatorial) embedding consists of cyclic orderings of the incident edges at each vertex. Given such an embedding there are multiple approaches discussed in literature to drawing the graph (subject to various constraints, e.g. integer coordinates), see e.g. [2].

The planarity check algorithm and extraction of the combinatorial embedding is based on the Left-Right Planarity Test [1].

A counterexample is only generated if the corresponding parameter is set, because the complexity of the counterexample generation is higher.

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

When G is planar, a PlanarEmbedding instance is returned:

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