Planar graphs are graphs that can be drawn on a plane without any intersecting edges. In order to draw them, you have to start from a vertex, draw from edge to edge, and keep track of the faces as the drawing continues. According to Kuratowski, a graph is planar if it does not contain a subgraph that is part of the complete graph on five vertices.
The following is a simple example of a planar graph:
Euler's formula connects a number of vertices, edges, and faces. According to Euler's formula, if a finite and connected planar graph is drawn in the plane without any intersecting edge, and if v represents the number of vertices, e represents the number of edges, and f represents the number of faces, then v − e + f = 2.
Besides Mayavi
, NetworkX
, and planarity
, you can use the gamera
package to create and display graphs. However, gamera
is only available on Windows. We have a simple example here that uses planarity
and NetworkX
:
import planarity import networkx as nx # complete graph of 8 nodes, K8 G8=nx.complete_graph(8) # K8 is not planar print(planarity.is_planar(G8)) # Will display false because G8 is not planar subgraph K=planarity.kuratowski_subgraph(G8) # Will display the edges print(K.edges()) #Will display the graph nx.draw(G8) False [(0, 4), (0, 5), (0, 7), (2, 4), (2, 5), (2, 7), (3, 5), (3, 6), (3, 7), (4, 6)]
This example illustrates that the following complete graph of eight nodes is not planar:
The preceding diagram shows that a planar graph with only eight nodes could look messy, so a graph with more nodes will look more complex.