The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
70 views

How to Find Whether Given Graph is NonPlanar using Kuratwoski's Theorem  ?

asked in Graph Theory by (93 points)
retagged by | 70 views

1 Answer

0 votes

The result to be utilised here is that K3,3(complete bipartite graph with 3 vertices in each partition) and k5(5 vertex complete graph) are simplest non-planer graphs.

KURATOWSKI THEOREM: ANY GRAPH WHICH CONTAINS SUBGRAPHS HOMEOMORPHIC TO K3,3 OR K5 ARE NON-PLANER (NOTE THAT IT IS AN IF AND ONLY IF CONDITION).

A graph is non-planar iff we can turn it into K3,3 or K5 by:

  1. Removing edges and vertices. (Making a subgraph.)

  2. Collapsing degree-two vertices into a single edge.

  3. Applying an isomorphism to turn it into K3,3 or K5.

In the above graph , 

  1. remove vertex e
  2. put {a,d,g} in one partition
  3. put {b,c,f} in other partition
  4. remove edges between {a,d},{a,g},{g,d},{b,c},{b,f},{f,c}

REMAINING GRAPH

answered by Junior (819 points)

Related questions

+1 vote
1 answer
7


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,311 questions
49,802 answers
164,505 comments
65,865 users