0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Can you give a reference for the paper? Can you be more specific about your source of confusion? $\endgroup$ – Juho Apr 17 '14 at 13:53
  • $\begingroup$ We expect you to do research on your own. What research have you done? Have you tried working through some examples? They include a definition in their paper of exactly what they mean by "equivalent intervals". What exactly don't you understand? If you are not familiar with reading math and expanding formal definitions and you're looking for someone to do that for you, this probably isn't the right site for that -- you might want to spend more time getting experience with algorithms and theoretical computer science, so you are able to read this kind of material on your own. $\endgroup$ – D.W. Apr 17 '14 at 23:59
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ could you please explain the concept of L-block and R-block $\endgroup$ – ishan3243 Apr 20 '14 at 13:06
  • 1
    $\begingroup$ The idea is to arrange all endpoints of all intervals in increasing order. Some of these are left endpoints and some are right endpoints. Divide them into runs on left endpoints and right endpoints. These are the L-blocks and R-blocks, respectively. $\endgroup$ – Yuval Filmus Apr 20 '14 at 20:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.