Graph Theory Cutwidth

Question

Can someone explain to me what is the cutwidth of an Interval Graph and give me an example for it?

I found this definition, but I don't understand it:

The cutwidth of a graph G is equal to the minimum cost of an ordering of its vertices.

Answer 1

Your definition is a bit incomplete: You should also include a definition of the cost associated with an ordering of the graph. In the definition you are probably referencing, this cost is defined as follows:

For any set S of nodes, the corresponding cost c'(S) is given by the number of edges going from any node in S to any node outside S

From this, the cost of an ordering v_1, ..., v_n is defined as the maximum cost of all subsets v_1, ..., v_i where i = 1, ..., n - 1
Based on the previous definition, this means you take the maximum number of edges that go from nodes of lower order to nodes of higher order, where you can choose the 'cut' between lower and higher order arbitrarily.

The cutwidth then is the cost of an optimal ordering of the nodes (i.e. the node ordering with minimal cost).

When we apply this to an interval graph, meaning a graph whose nodes are intervals and whose edges represent intersections between these intervals, the cost c'(S) of a subset is the number of intersections between intervals outside S with intervals inside S.

From this, you can see that the cutwidth of an interval graph is the cost of the optimal ordering of the intervals such that higher-order intervals intersect with lower-order intervals the least amount of times.

Unfortunately, I cannot give you an exact calculation rule for what this cutwidth is for a given interval graph, but I'll give you a small example:

Take the intervals [0,4],[0,1],[2,3],[1.5,2.5],[3.5,5] which give the following graph:

No matter how you order the intervals, if you have chosen two intervals in the 4-cycle [0,4],[0,1.9],[1.5,2.5],[2,3] to go first in your order, the other two intervals in the cycle will have at least two intersections with the first two intervals, which means that the cutwidth is at least 2.

At the same time, the ordering [0,1.9],[1.5,2.5],[2,3],[0,4],[3.5,5] gives you a cut cost of 2,2,2,1 for i = 1,2,3,4, so the cutwidth of this graph is at most 2.

Combining these results, you can see that the cutwidth of the graph is 2.

It might be possible to generalize this kind of upper and lower bound on the cutwidth to all interval graphs, but I can't give you a complete solution for that problem at the moment.