Constructing a permutation graph

Question

I have read about how permutation graphs make many NP-complete problems a lot easier to solve. For example, the maximal clique problem, tree width problem etc. However, I am unable to understand the process of creating a permutation graph from a given graph G(V,E). How would one go about doing this?

Answer 1

You do not create a permutation graph from a graph, but from a permutation. The process is quite simple:

1. write numbers 1 to n on a line, then
2. write them again on a separate, parallel line according to the order in which they appear in your permutation;
3. connect each element from the first line to the same element on the second line (1 to 1, 2 to 2, ..., n to n),
4. label each such connection with the numbers that it connects (e.g. connection 2 to 2 receives label 2);
5. the resulting permutation graph is obtained by treating each connection as a vertex and connecting two vertices whenever the corresponding connections intersect.

If that's still unclear, see the nice example on Wikipedia.

It is clear from the process that such a graph can always be constructed from any permutation; however, having a permutation graph may lead you to deduce several permutations that correspond to it.