- 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.
- GNetworkX graph
A Kuratowski subgraph (to proof non planarity) is only returned if set to true.
- (is_planar, certificate)(bool, NetworkX graph) tuple
is_planar is true if the graph is planar. If the graph is planar
certificateis a PlanarEmbedding otherwise it is a Kuratowski subgraph.
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. .
The planarity check algorithm and extraction of the combinatorial embedding is based on the Left-Right Planarity Test .
A counterexample is only generated if the corresponding parameter is set, because the complexity of the counterexample generation is higher.
Ulrik Brandes: The Left-Right Planarity Test 2009 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.217.9208
Takao Nishizeki, Md Saidur Rahman: Planar graph drawing Lecture Notes Series on Computing: Volume 12 2004