Given N sets and all pairs of non-empty intersections between those sets, can those N sets be real number intervals?

Question

Thanks to @LordSharkOfTheUnknown, I now realize that I wish to recognize if a graph is an interval graph. He had linked this Wikipedia article of the subject, but I have not understood the recognition algorithm described there

I was solving a question in Stack Overflow in Portuguese about a particular problem that could be modeled as graph-colouring. The problem was something like this:

I have n machines. Those machines needs to work at continuous intervals: I_1 for the first machine, I_2 for the second and so on. Each machine needs one operator to work properly, and each operator can only handle a single machine at a given time. What is the minimum number of operators needed?

So, I have modeled this as a graph:

• each vertex k is a machine k/time interval I_k
• each edge connecting vertex j and k is a time overlap between intervals I_j and I_k; or equaly it is a non-empty intersection between I_j and I_k
• each vertex colour is an operator, so no operator can operate two similtaneous machines, thus one colour cannot be it's own neighbor

So far, everything is fine. But, given a graph, can it have the semantics above? This can also be asked as the title question:

• Given n sets and a list of all pairs of sets that has non-empty intersections, can all of those sets be continuous intervals of real numbers?

So far, I know that this problem lies in NP, because if I have a list of intervals for each set, than I can test if all the intersections apply and validate if is a correct input.

---

For example, a valid input:

Given 4 sets (A,B,C,D) with the following intersections:

• A,B
• B,C
• C,D
• A,D
• B,D

It is a valid graph. Because I can have this values:

• A = [1,10]
• B = [8,15]
• D = [8,14]
• C = [12,18]

All the intersections above occurs, thus these intervals represents a valid input

---

For example, an invalid input:

Given 4 sets (A,B,C,D) with the following intersections:

• A,B
• B,C
• C,D
• A,D

There are no such values for A, B, C and D so that they are continuous intervals ou real numbers and there exista only those 4 non-empty intersections

---

• Original question that I was solving: Escalonamento de máquinas - Teoria dos Grafos
• SOpt question of this same open question: Como identificar um grafo inválido para problema de alocação de operadores por máquina?