A graph 
is an interval graph if it captures the intersection relation for some set of intervals
on the real line. Formally, 
is an interval graph provided that one can assign to each
an interval 
such that 
is nonempty precisely when 
. An interval graph on a list 
can be generated using IntervalGraph[l]
in the Wolfram Language package Combinatorica`
.
Star graphs are interval graphs, but cycle graphs (for 
)
are not (Skiena 1990, p. 164). Determining if a graph is an interval graph and
realizing it can be done in 
time (Booth and Lueker 1976; Skiena 1990, p. 164).
A graph 
is an interval graph iff the vertices of 
can be ordered 
, ..., 
such that 
adj 
implies 
adj 
whenever 
(West 2000, p. 346).
Every induced subgraph of an interval graph is itself an interval graph (Jacobson et al. 1991; West 2000, p. 226).
