How to check if a Graph is a Planar Graph or not?

Question

I'm learning about the Planar Graph and coloring in c++. But i don't know install the algorithm to do this work. Someone please help me?

Here i have some information for you! This is my code! And it still has a function does not finish. If someone know what is a "Planar Graph", please fix the Planar_Graph function below! :D thanks so much! :x

# define MAX 100

int kt[MAX];
int tk=0;

int my_array[MAX][MAX];      // Graph
FILE *f;
int n,m;            //m: Edge, n: Vertex
int index[MAX];            
int ke[MAX];      
int Color[MAX]   ;      //Color Array
int colors_max;      
char filename[MAX];

int input(char filename[MAX])   
{
    int i,j;

    f = fopen(filename,"r");
    if (f== NULL)
    {
        printf("\n Error \n");
        return 1;
    }
    else
    {
        printf("File mane: %s \n",filename);
        printf("Content   :\n");
        fscanf(f,"%d",&n);
        fscanf(f,"%d",&m);

        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            {
                fscanf(f,"%d",&my_array[i][j]);
                printf("%d   ",my_array[i][j]);
            }
            printf("\n");
        }      
        return 0;
    }   
}

void Default()   

{
    for(int i=0;i<colors_max;i++)
    Color[i]= i;
}

void Init()             
{
    filename[0]=NULL;
    n = 0;
}


int Planar_Graph(int my_array[MAX][MAX],int n, int m) // This is my problem
{

    /* for(int i=0;i<n;i++)

        if(n>=2 && (int)(n+1)*(n-2)/(n-1)>=m)
        return 1;
    }
    else
    {
        return 0;
    } */

}

int max()
{
    int max;
    int count=0;
    for(int i=0;i<n;i++)
    {       
        count = 0;
        for(int j=0;j<n;j++)   
            if (my_array[i][j] > 0)   
                count++ ;
        if (max < count)      
            max = count;
    }
    return max+1;
}

void Check(int x,int y)      // Check around
{
    int i;
    Default();         
    for(i=0;i<n;i++)
    {
        if (my_array[x][i] != -1)   // if edge [x,ke[i]] is color t
            Color[my_array[x][i]] = -1;   // then Color[t] = 0
    }

    for(i=0;i<n;i++)
    {
        if (my_array[y][i] != -1)
            Color[my_array[y][i]] = -1;

    }
}

void Coloring()
{
    int t;
    for(int i=0;i<n;i++)
      for(int j=0;j<n;j++)
         if (my_array[i][j] > 0)
         {
            Check(i,j) ;
            for(t=0;t < colors_max;t++)
               if (Color[t] == t)
               {
                  my_array[i][j] = t;
                  my_array[j][i] = t;
                  break;
               }
         }
}

void main()
{

    if(input("input.txt")!=1)
    {
         Default();
         colors_max =  max()    ;
         Coloring();
         printf("\n Result:\n\n");
         Planar_Graph(my_array,n,m);
         for(int i=0;i<n;i++)
         {
              for(int j=0;j<n;j++)
                if (my_array[i][j]>0)
                {
                    printf(" %c,%c] coloring %d \n",i + 'A',j + 'A',my_array[i][j]) ;
                    my_array[i][j] = -1;
                    my_array[j][i] = -1; 
                }
                printf("\n") ;
         }

    }

}

The input file example:

10 18
0 1 0 1 1 1 0 0 0 0
1 0 1 0 0 0 0 0 0 0
0 1 0 0 1 0 0 0 0 0
1 0 0 0 1 0 1 1 0 0
1 0 1 1 0 1 1 0 1 0
1 0 0 0 1 0 1 0 1 0
0 0 0 1 1 1 0 1 0 0
0 0 0 1 0 0 1 0 1 1
0 0 0 0 1 1 0 1 0 1
0 0 0 0 0 0 0 1 1 0

Solution 1

Regarding planarity...

The well known e <= 3v - 6 criteria by Euller mentioned here says that if a graph is planar, then that condition must hold. However, not all graphs in which that condition holds are necessarily planar. That is why you actually need a planarity test algorithm.

A thing to notice is that planarity testing algorithms are not easy to implement. There's a very old one which is based on subgraphs finding and removal. I can't remember the original authors right now, but the problem with their algorithm is that it has O(n³) complexity.

The first planarity test algorithm considered to be efficient - O(n) in the case - is due to Hopcroft and Tarjan. This was already mentioned here in the post by Yin Zhu. You can find the original paper here.

This time, the problem with the algorithm was that many people found it too hard to understand and even to implement. So there are papers with the intention of just clarifying points of the original paper. For instance, the Kocay paper.

The Hopcraft-Tarjan paper is classic and if you want to try to implement it, the best reference I have is this other paper, which presents the theory together with a C++ implementation. That was written by the people who implemented the algorithm in the LEDA library.

Years later after the Hopcroft-Tarjan paper (which was in 1974), others O(n) algorithms were published. I don't know much about them, but some used PC/PQ trees. There is one, however, which I read and found very interesting. It's due to Boyer and Myrvold and it's from 2004. You can find it here. Besides the algorithm itself, of course, a good thing about this paper is that it provides a rigorous historical reference about planarity test algorithms.

Very recently, I discovered a another paper from 2008 in which Tarjan is one of the authors. Haven't checked it yet.

Well, if you got tired just by reading this post, I assume you don't want to implement your own algorithm. :) In this case, I can recommend some C++ libraries.

• Boost.
• GDToolkit.
• LEDA.
• OGDF.
• GTAD - This is my own graph library (which, unfortunately, I haven't been able to work on it lately). There's an implementation of the Hopcroft-Tarjan algorithm, which I wrote based on that paper I mentioned. Since the paper already provides real code, things are a lot easier.

Solution 2

Testing an undirected graph planar or not is well-solved and there exist efficient algorithms. It is actually part of R. Tarjan's 1986 Turing award work.

You can first check this note. http://bkocay.cs.umanitoba.ca/G&G/articles/Planarity.pdf

You may also want to check Tarjan and Hopcraft's orginal paper: http://portal.acm.org/citation.cfm?id=321852

I don't know if there have been significant advances in the algorithms. But T&H's algorithm is already very fast.

btw, implementing the algorithm is very hard and the theorem in wiki page does not give you an efficient implementation clue(though easy).

Solution 3

Your question appears to cover two topics: - is a graph planar? (your title) - (if so?) how can I color it (you don't say how many colors).

For the first part Wikipedia has a useful section: http://en.wikipedia.org/wiki/Planar_graph

You should read it in full, but it gives two simple requirements for planarity:

For a simple, connected, planar graph with v vertices and e edges, the following simple planarity criteria hold:

Theorem 1. If v ≥ 3 then e ≤ 3v − 6;
Theorem 2. If v > 3 and there are no cycles of length 3, then e ≤ 2v − 4.

You will need to create a data structure capable of holding vertices and edges and then you will need to be able to determine cycles of length 3 (triangles).