10768 - Planarity

[sohel]

I simply did what they asked me to do.. ie

- remove all the nodes of degree one and the associated edge with those.
- remove those with degree 2 and join the corresponding pairs.

then I do an exhaustive search to find K5, or K3,3..

Is there anything that I missed?

[misof]

I simply did what they asked me to do.. ie

- remove all the nodes of degree one and the associated edge with those.
- remove those with degree 2 and join the corresponding pairs.

then I do an exhaustive search to find K5, or K3,3..

Is there anything that I missed?

First of all, I was told by a friend that during the contest this solution would be accepted. If they didn't change the test cases, it should still be accepted.

However, I did not write this solution during the contest because of the following reasons:

This approach is NOT correct when testing for planarity. Also the Kuratowski theorem is NOT stated correctly in the problem statement.

The correct statement is: A graph is planar IFF it doesn't contain a subgraph homeomorphic to K_5 or K_{3,3}.

An example on where's the difference: Let N=9. Make a K_5 on vertices 1,2,3,4,5. Delete the edge 4-5. Add edges 4-6, 5-6. Make a K_4 on vertices 6,7,8,9. This graph cannot be reduced and thus it is NOT homeomorphic to any graph containing K_5 or K_{3,3}. But it's subgraph (induced by vertices 1,2,3,4,5,6) IS homeomorphic to K_5 and THEREFORE this graph is NOT planar. (The problem statement says that it is.)

Does anybody know whether the test data was changed?

[Per]

It wasn't. Or if it was, there are no cases in the judge input where the heuristic described in the problem statement does not work.

[sohel]

Does that mean, there is something wrong with my code.

And is there any other way of detecting whethere a graph is planar or not.
I heard there is an O(n) soln for it. Can someone confirm its validity.

[Per]

Yeah there is, though it is very complicated.

http://portal.acm.org/citation.cfm?id=321850.321852

[Mohammad Mahmudur Rahman]

Well, being completely aware of the fact that there is no very easy algorithm known for detecting planarity, I tried to approach the problem in an alternative manner rather than Kuratowaski's theorem. Though this method ultimately resulted into a WA during the contests, it passed all the different test cases that I could think of.

I found some corrolaries related to Euler's formula about planarity in the book Discrete Mathematics & applications by Kenneth H. Rosen


Corollary 1 If G is a connected planar simple graph with e edges & v vertices where v>=3, then e<= 3v-6. (Section 8.7, Page 607)
But this formula doesn't hold good for some cases. So there occurs corollary 3.

Corollary 3 If a connected planar simple graph has e edges & v vertices with v>=3 & no circuits of length 3, then e<= 2v-4 (Section 8.7, Page 609)

& finally -
Formula X If G is a connected plannar simple graph with e edges & v vertices with no simple circuits of length 4 or less, then e<=(5/3)v - (10/3) (Exercise 17, page 612)

Now my idea is as follows -

Code: Select all

1) Surely no non-planar graph can be formed with less than 5 vertices. So, if V<5 print YES & exit.

2) Reduce the graph using the conditions given in the problem while possible.

3) Find the length of the cycles existing in the graph if there is any using a DFS traversal.

4) If the graph has no cycle of length 3/4 then use Formula X stated above to test planarity & exit.

/* Surely a circuit of length 4 or less means length 3/4 as there can be no circuit of length 1/2.*/
/* If the IF check of step 4 works then the graph either has no circuit or circuit(s) of length>4. Else the graph must has a circuit of length 3/4.*/

5) If the graph has a circuit of length 4 then use Corollary 3 to detect planarity & exit.

6) If neither 4 nor 5 works, the graph must has a circuit of length 3. use Corollary 1. [i]I have confusions here.[/i]

As I am new to graph theory, will someone please spend some time & figure out my error? Thanks a lot for reading this long post.

[CDiMa]

Code: Select all

1) Surely no planar graph can be formed with less than 5 vertices. So, if V<5 print NO & exit.

hmm, what about this?

Code: Select all

1 0
2 1
1 2
3 3
1 2
2 3
3 1

Ciao!!!

Claudio

[misof]

Code: Select all

1) Surely no planar graph can be formed with less than 5 vertices. So, if V<5 print NO & exit.

As Claudio already said, this is wrong. In fact, exactly the opposite holds -- no NON-planar graph can be formed on less than 5 vertices, because K_4 is planar.

Formula X If G is a connected plannar simple graph with e edges & v vertices with no simple circuits of length 4 or less, then e<=(5/3)v - (10/3) Exercise 17, page 612

Code: Select all

4) If the graph has no cycle of length 3/4 then use Formula X stated above to test planarity & exit.

This is wrong too. Formula X is just an implication. It says "IF G is connected planar, THEN ..." -- or equivalently, "IF NOT ... THEN G is not connected planar". In the case when e<=(5/3)v - (10/3) your formula says nothing about the planarity of G. One can easily construct a connected non-planar graph with less than (5/3)v - (10/3) edges.

[Mohammad Mahmudur Rahman]

Mohammad Mahmudur Rahman wrote:
Code:
1) Surely no planar graph can be formed with less than 5 vertices. So, if V<5 print NO & exit.


As Claudio already said, this is wrong. In fact, exactly the opposite holds -- no NON-planar graph can be formed on less than 5 vertices, because K_4 is planar.

Thanks guys. It was a bad slip of key-board. which eompletely inverted the simple idea. It has been corrected now.

Meanwhile, Claudio's input contained multiple edges which I think will not be present in the input according to the problem statement - "There are no repeated edges."


Thanks to Misof for pointing out the error in Step 4. But can you give some test cases that breaks this step?

Thanks a lot.

[CDiMa]

Meanwhile, Claudio's input contained multiple edges which I think will not be present in the input according to the problem statement - "There are no repeated edges."

My example doesn't contain multiple edges. To make it clearer:
Case 1(1 vertex no edges, clearly planar )

Code: Select all

1 0 

Case 2 (2 vertices, 1 edge)

Code: Select all

2 1 
1 2

Case 3 (3 vertices, 3 edges)

Code: Select all

3 3 
1 2 
2 3 
3 1

Ciao!!!

Claudio

[Mohammad Mahmudur Rahman]

Thanks a lot for the explanation, Claudio. Now I fully understand it.

[ReiVaX18]

...
An example on where's the difference: Let N=9. Make a K_5 on vertices 1,2,3,4,5. Delete the edge 4-5. Add edges 4-6, 5-6. Make a K_4 on vertices 6,7,8,9. This graph cannot be reduced and thus it is NOT homeomorphic to any graph containing K_5 or K_{3,3}. But it's subgraph (induced by vertices 1,2,3,4,5,6) IS homeomorphic to K_5 and THEREFORE this graph is NOT planar. (The problem statement says that it is.)

Does anybody know whether the test data was changed?

It's homeomorphic to itself, that contains the subgraph K_5, so the problem statement says it's not planar.

[medv]

#include <stdio.h>
#include <memory.h>

double a[21][21];
int degree[21];
int c[7];
int m,n;

int main(void)
{
int i,j,x,y;
int temp;
while(scanf("%d %d\n",&n,&m) == 2)
{
memset(a,0,sizeof(a));
memset(degree,0,sizeof(degree));
for(j=1;j<=m;j++)
{
scanf("%d %d\n",&x,&y);
if(!a[x][y])
{
degree[x]++; degree[y]++;
a[x][y] = a[y][x] = 1;
}
}
for(i=1;i<=n;i++)
{
if (degree[i] == 1)
for(j=1;j<=n;j++)
if (a[i][j])
{
a[i][j] = a[j][i] = 0;
degree[i] = 0;
degree[j]--;
}
if (degree[i] == 2)
{
for(j=1;j<=n;j++)
if (a[i][j])
{
temp = j;break;
}
for(j=temp+1;j<=n;j++)
if (a[i][j])
{
a[i][j] = a[j][i] = 0;
a[i][temp] = a[temp][i] = 0;
degree[i] = 0;
if (a[j][temp])
{
degree[j]--; degree[temp]--;

} else
{
a[j][temp] = a[temp][j] = 1;
}
}
}
}
temp = 1;
for(c[1]=1;c[1]<=n-4;c[1]++) if (degree[c[1]])
for(c[2]=c[1]+1;c[2]<=n-3;c[2]++) if (degree[c[2]])
for(c[3]=c[2]+1;c[3]<=n-2;c[3]++) if (degree[c[3]])
for(c[4]=c[3]+1;c[4]<=n-1;c[4]++) if (degree[c[4]])
for(c[5]=c[4]+1;c[5]<=n;c[5]++) if (degree[c[5]])
{
x = 1;
for(i=1;i<=5;i++) if (x)
for(j=1;j<=5;j++)
if (!a[c[i]][c[j]])
{
x = 0; break;
}
if (x) {temp = 0; goto ff1;}
}
for(c[1]=1;c[1]<=n-2;c[1]++) if (degree[c[1]])
for(c[2]=c[1]+1;c[2]<=n-1;c[2]++) if (degree[c[2]])
for(c[3]=c[2]+1;c[3]<=n;c[3]++) if (degree[c[3]])
for(c[4]=c[1]+1;c[4]<=n-2;c[4]++) if ((degree[c[4]]) && (c[4] != c[2]) && (c[4] != c[3]))
for(c[5]=c[4]+1;c[5]<=n-1;c[5]++) if (degree[c[5]] && (c[5] != c[2]) && (c[5] != c[3]))
for(c[6]=c[5]+1;c[6]<=n;c[6]++) if (degree[c[6]] && (c[6] != c[2]) && (c[6] != c[3]))
{
x = 1;
for(i=1;i<=3;i++) if (x)
for(j=4;j<=6;j++)
if (!a[c[i]][c[j]])
{
x = 0; break;
}
if (x) {temp = 0; goto ff1;}
}
ff1:;
if(temp) printf("YES\n");
else printf("NO\n");
}
return 0;
}

[prince56k]

just replce "#include<memory.h>" with
""#include<string.h>"


pls post code in c/c++ formatted way.

[medv]

It does not help

I even deleted #include <memory.h>
I rewrote

for(i=0;i<=n;i++)
for(j=i;j<=n;j++)
a[i][j] = a[j][i] = 0;
for(i=0;i<=n;i++)
degree[i] = 0;

WHY Compile Error???
I spent a night on it!!!