#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>> G;
bool no_update = true;
int n,m;
void remove_self_loop()
{
for(int i=0; i<G.size(); i++) {
if(G[i].first == G[i].second)
{
G.erase(G.begin()+i);
i--;
}
}
}
void remove_parallel_edge()
{
for(int i=0; i<G.size(); i++)
{
for(int j=i+1; j<G.size(); j++) {
if(G[i].first == G[j].first && G[i].second == G[j].second)
{
G.erase(G.begin()+j);
j--;
}
}
}
}
int find_degree(int vertex){
map<int, int> m;
for (int i = 0; i <G.size(); i++)
{
m[G[i].first]++;
m[G[i].second]++;
}
return m[vertex];
}
void remove_2_degree_vertex()
{
for(int i=0; i<n; i++)
{
// cout<<"degree : "<<find_degree(i)<<endl;
if(find_degree(i)==2)
{
no_update = true;
vector<int> v1;
for(int j = 0; j < G.size(); j++)
{
if(G[j].first==i)
{
v1.push_back(G[j].second);
G.erase(G.begin()+j);
j--;
}
if(G[j].second==i)
{
v1.push_back(G[j].first);
G.erase(G.begin()+j);
j--;
}
if(v1.size()==2)
break;
}
if(v1[0]>v1[1])
swap(v1[0],v1[1]);
G.push_back(make_pair(v1[0],v1[1]));
remove_parallel_edge();
}
}
}
int main()
{
cout<<"Enter the number of vertices : ";
cin>>n;
cout<<"Enter the number of edges : ";
cin>>m;
cout<<"Enter graph : ";
for(int i=0;i<m;i++)
{
int a,b;
cin>>a>>b;
if(a>b)
{
swap(a,b);
}
G.push_back(make_pair(a,b));
}
while(no_update)
{
no_update = false;
remove_self_loop();
remove_parallel_edge();
remove_2_degree_vertex();
}
/*cout<<"\n--------------------------------\n";
for(int i = 0; i <G.size(); i++)
{
cout<<""<<G[i].first<<"--"<<G[i].second<<endl;
}
cout<<"--------------------------------\n";*/
map<int, int> l;
for(int i = 0; i < G.size();i++)
{
l[G[i].first]++;
l[G[i].second]++;
}
int edges = G.size();
int vertices = l.size();
if(edges==1)
{
cout<<"The given Graph is Planner.\n";
return 0;
}
//For a connected planar graph G = (V, E) with n vertices, m edges and f
faces, n - m + f = 2.
//The number of edges in a maximal planar graph is 3n-6
//Let G be a planar graph of order n and size m. Then, m ≤ 3n-6.
//There is a vertex of degree at most five in any planar graph G.
//The number of edges in a planar bipartite graph of order n is at most
2n-4
//K5 is non planar.
//K3,3 is non planar.
//A graph G is planar if and only if it does not any subgraph homeomorphic
to K5 or K3,3
//K3,3 is non planar.
if(edges == 9 && vertices == 6)
{
int count_degree_3 = 0;
for(int i = 0; i < vertices; i++)
{
if(l[i]==3)
count_degree_3++;
}
if(count_degree_3==6)
{
cout<<"Given graph is not planar graph\n";
return 0;
}
}
//K5 is non planar.
if(edges == 10 && vertices == 5)
{
int count_degree_4 = 0;
for(int i = 0; i < vertices; i++)
{
if(l[i]==4)
count_degree_4++;
}
if(count_degree_4==5)
{
cout<<"Given graph is not planar graph\n";
return 0;
}
}
//e<=3n-6 or e<=2n-4 //n>=5 && e>=7
if(vertices >= 5 && edges>= 7)
{
if((edges<=3*vertices-6) || (edges<=2*vertices-4))
{
cout<<"Given graph is planar graph\n";
return 0;
}
}
cout<<"Given graph is not planar graph\n";
return 0;
}
/*
5
9
0 1
0 2
1 2
1 3
1 4
2 4
4 2
3 4
3 3
*/
/*
5
7
0 1
0 2
0 3
0 4
1 4
1 2
2 3
*/
/*
K5
5
10
0 1
0 2
0 3
0 4
1 2
1 3
1 4
2 3
2 4
3 4
*/
/*
K3,3
6
9
0 3
0 4
0 5
1 3
1 4
1 5
2 3
2 4
2 5
*/
Comments
Post a Comment