Interval graph
In graph theory, an interval graph is the intersection graph of a family of intervals on the real line. It has one vertex for each interval in the family, and an edge between every pair of vertices corresponding to intervals that intersect.
Formally, an interval graph is an undirected graph formed from a family of intervals
by creating one vertex vi for each interval Si, and connecting two vertices vi and vj by an edge whenever the corresponding two sets have a nonempty intersection, that is,
From this construction one can verify a common property held by all interval graphs. That is, graph G is an interval graph if and only if the maximal cliques of G can be ordered M1, M2, ..., Mk such that for any v ∈ Mi ∩ Mk, where i < k, it is also the case that v ∈ Mj for any Mj, i ≤ j ≤ k.
Three vertices form an asteroidal triple in a graph G if, for each two, there exists a path containing those two but no neighbor of the third. A graph is AT-free if it has no asteroidal triple. The earliest characterization of interval graphs seems to be the following:
A graph is an interval graph if and only if it is chordal and AT-free.
Other characterizations:
A graph is an interval graph if and only if the edge clique cover of all of its maximal cliques can be arranged into a clique path representation.
A graph is an interval graph if and only if it is C4-free and its complement has a transitive orientation.
Various other characterizations of interval graphs and variants are mentioned in,.
Determining whether a given graph G = (V, E) is an interval graph can be done in O(|V|+|E|) time by seeking an ordering of the maximal cliques of G that is consecutive with respect to vertex inclusion.
The original linear time recognition algorithm of Booth & Lueker (1976) is based on their complex PQ tree data structure, but Habib et al. (2000) showed how to solve the problem more simply using lexicographic breadth-first search, based on the fact that a graph is an interval graph if and only if it is chordal and its complement is a comparability graph. A similar approach using a 6-sweep LexBFS algorithm is described in Corneil, Olariu & Stewart (2009).
...
Wikipedia