**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:**
**f**
**G**
**a**
**b**
**c**
**d**
**e**
**g**
**h**
**i**
**j**
**g**
**H**
**a**
**f**
**e**
**d**
**i**
**j**
**c**
**h**
**h**
**d**
**K3,3**
**f**
**e**
**j**
**i**
**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. **
**a**
**b**
**H**
**c**
**d**
**e**
**f**
**g**
**i**
**a**
**b**
**K5**
**c**
**g**
**i**
**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.**
**a**
**b**
**h**
**G**
**c**
**d**
**e**
**f**
**g**
**k**
**i**
**j**
**Share with your friends:** |