New sequential and parallel algorithms for interval graph recognition

A graph G = (V, E) is said to be an interval graph if each vertex in the graph can be associated with an interval in the real line such that two vertices are adjacent in the graph iff the two corresponding intervals intersect. The collection of intervals is called an interval representation of the graph.