Recognizing interval graphs--"equivalent intervals"

Question

I was reading a paper for recognizing interval graphs. Here is an excerpt from the paper:

Each interval graph has a corresponding interval model in which two intervals overlap if and only if their corresponding vertices are adjacent. Such a representation is usually far from unique. To eliminate uninteresting variations of the endpoint orderings, we shall consider the following block structure of endpoints: Denote the right (resp. left) endpoint of an interval $u$ by $R(u)$ (resp. $L(u)$). In an interval model, define a maximal contiguous set of right (resp. left) endpoints as an R-block (resp. L-block). Thus, the endpoints can be grouped as a left-right block sequence. Since an endpoint block is a set, the endpoint orderings within a block are ignored. It is easy to see that the overlapping relationship does not change if one permute the endpoint order within each block. Define two interval models for $G$ to be equivalent if either their left-right block sequences are identical or one is the reversal of the other.

I am unable to understand the notion of equivalent intervals. Can someone help me?

Answer 1

Imagine scanning the real line from left to right. Whenever an interval starts or ends, you make notice of it. For example, perhaps at some representation, at the point $3$ the intervals for $x_2,x_7$ start and the interval for $x_{15}$ ends, and at the point $4$ the interval for $x_2$ ends, and no points occur in between.

Suppose we "remove" the portion $(3.25,3.75)$ of the real line, thus pushing the point $4$ back to $3.5$. This only affects the value of some ordinates, so we would like to say that these two interval representations are "the same". Indeed, they are equivalent under the definition you give, since if we make a list of which intervals start and end at what point, then the lists would be identical, the only difference being the value of the ordinates.

Another operation we can do is reflecting the real line, say around zero. Now the interval for $x_2$ is $(-4,-3)$ instead of $(3,4)$, so that at the point $-4$ the interval $x_2$ starts, and at the point $-3$ the intervals for $x_2,x_7$ end and the interval for $x_{15}$ starts. Again, we would like both of these representation to count as "the same". This transformation is captured by the reversal clause in the definition you quote.