check_planarity

check_planarity(G, counterexample=False)

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.

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