### Example: Recognizing interval graphs

Since intervals obey the
Helly-property,
all cliques in an
interval graph
are star graphs.
There are more star graphs, but we may neglect them in the remaining
layout step of the recognition algorithm; we may discretize.
Let *a*_{1}*, a_{2}*, ... , a_{k}* be the cliques, and define
*S*_{x}` as the set of all those points *a* where
*x a**.
The question is whether or not there is some placement of these detectors
*a*_{1}, a_{2}, ... , a_{k} on the real line such that *S*_{x}`
forms a consecutive part among all detectors, for every vertex *x*.

A **concrete interval hypergraph** has vertex set
{*1,2, ... , n*}
and all hyperedges have the form {*i,i+1, ... , j*}.
An **interval hypergraph** is any hypergraph isomorphic
to some concrete
interval hypergraph. So we have the hypergraph,
but have forgotten the vertex labels.
The question above is how to recognize interval hypergraphs.
Surely we have no time to test all *n!* vertex labelings.

In matrix theory, this problem is known under the consecutive-ones problem.
A 0-1 matrix has the consecutive-ones property for rows if the columns
can be permuted in such a way that the ones in each row appear consecutively.
A hypergraph is an interval hypergraph if and only if its incidence matrix
has the consecutive-ones property for rows.
It is possible, though rather involved, to recognize this property
in linear time, but since this has few to do with intersection graphs,
we will omit the proof.

**[BL76]:**
*Interval hypergraphs can be recognized in linear time.* |

Note that there are quite a few more characterizations leading to efficient
recognition algorithms for interval graphs.
In all of them, the linearity and ordering of the model is cruical.

Erich Prisner

made on January 12, 1999