Lesson 2

Theorem (Kuratowski). A graph is planar if and only if it contains no subgraph that is a subdivision of \(K_{3,3}\) or \(K_{5}\) (in other words, it is impossible to delete some vertices and edges so that what remains is a subdivision of  \(K_{3,3}\) or \(K_{5}\)).

There are linear algorithms that not only check this property but also return an embedding if the graph is planar, or a corresponding subgraph that is a subdivision of \(K_{3,3}\) or \(K_{5}\) if the graph is not planar. The example below shows that the Petersen graph contains a subgraph that is a subdivision of \(K_{3,3}\).

import networkx as nx
import matplotlib.pyplot as plt

import ast_parser.environment.figure_envs

g = nx.petersen_graph()
is_planar, subdivision = nx.check_planarity(
    g, counterexample=True
)

ast_parser.environment.figure_envs.figure().gca().set_axis_off()
pos = {7: [0, 0], 3: [1, 0], 6: [2, 0], 8: [0, 1],
       5: [0, 0.5], 9: [1, 1], 2: [2, 1],
       1: [2, 0.5], 4: [1, 0.25]}
nx.draw_networkx(subdivision, pos, with_labels=False,
                 node_color='skyblue')
plt.savefig('subdivision.png')