To Obtain G2 from G1, we can use this elementary subdivisions

To Obtain G2 from G1, we can use this elementary subdivisions:

To Obtain G2 from G1, we can use this elementary subdivisions:

• Remove the edge {a , c}, add the vertex f, and add the edges {a , f} and {f , c}
• Remove the edge {b , c}, add the vertex g, and add the edges {b , g} and {g , c}
• Remove the edge {b , g}, add the vertex h, and add the edges {b , h} and {h , g}

Kuratowski’s Theorem

Kuratowski’s Theorem

(Planarity Testing Algorithm)

A graph is nonplanar if and only if it contains a subgraph homeomorphic to k3,3 or k5 .

(NOTE: A graph obtained by removing a vertex and its associated edge of a graph is the subgraph of that graph.)

Illustration:

Illustration:

• Graph G is the Petersen Graph.
• H is a subgraph of G obtained by removing vertex b and edges {b , g},{b , a} and {b , c}.
• Subgraph H is Homeomorphic to K3,3.
• Hence, G is nonplanar.

• Here graph G is an Undirected Graph with the given vertices and edges.
• H is a subgraph of G obtained by deleting h, j, and k and edges { i, g }, { g, c }, { c, c }.
• Subgraph H is homeomorphic to k5 .
• Hence graph G is nonplanar.