check_planarity(G, counterexample=False)
A graph is planar iff it can be drawn in a plane without any edge intersections.
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.
A Kuratowski subgraph (to proof non planarity) is only returned if set to true.
is_planar is true if the graph is planar. If the graph is planar :None:None:`certificate` is a PlanarEmbedding otherwise it is a Kuratowski subgraph.
Check if a graph is planar and return a counterexample or an embedding.
is_planar
Check for planarity without creating a :None:None:`PlanarEmbedding` or counterexample.
>>> 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]}See :
The following pages refer to to this document either explicitly or contain code examples using this.
networkx.algorithms.planarity.PlanarEmbedding
networkx.algorithms.planarity.is_planar
networkx.algorithms.planarity.check_planarity
Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.
Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)
SVG is more flexible but power hungry; and does not scale well to 50 + nodes.
All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them