Presenters: presenters


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



Download 249.09 Kb.
Page2/9
Date20.07.2021
Size249.09 Kb.
#57089
1   2   3   4   5   6   7   8   9
roll-25-29

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

Download 249.09 Kb.

Share with your friends:
1   2   3   4   5   6   7   8   9




The database is protected by copyright ©ininet.org 2024
send message

    Main page