Many important graph families can be described as intersection graphs of more restricted types of set families, for instance sets derived from some kind of geometric configuration: • An
interval graph is defined as the intersection graph of intervals on the real line, or of connected subgraphs of a
path graph. • An
indifference graph may be defined as the intersection graph of unit intervals on the real line • A
circular arc graph is defined as the intersection graph of
arcs on a circle. • A
polygon-circle graph is defined as the intersection of polygons with corners on a circle. • One characterization of a
chordal graph is as the intersection graph of connected subgraphs of a
tree. • A
trapezoid graph is defined as the intersection graph of trapezoids formed from two parallel lines. They are a generalization of the notion of
permutation graph, in turn they are a special case of the family of the complements of
comparability graphs known as cocomparability graphs. • A
unit disk graph is defined as the intersection graph of
unit disks in the plane. • A
circle graph is the intersection graph of a set of chords of a circle. • The
circle packing theorem states that
planar graphs are exactly the intersection graphs of families of closed disks in the plane bounded by non-crossing circles. •
Scheinerman's conjecture (now a theorem) states that every planar graph can also be represented as an intersection graph of
line segments in the plane. However, intersection graphs of line segments may be nonplanar as well, and recognizing intersection graphs of line segments is
complete for the
existential theory of the reals . • The
line graph of a graph
G is defined as the intersection graph of the edges of
G, where we represent each edge as the set of its two endpoints. • A
string graph is the intersection graph of
curves on a plane. • A graph has
boxicity k if it is the intersection graph of multidimensional
boxes of dimension
k, but not of any smaller dimension. • A
clique graph is the intersection graph of
maximal cliques of another graph • A
block graph or clique tree is the intersection graph of
biconnected components of another graph characterized the
intersection classes of graphs, families of finite graphs that can be described as the intersection graphs of sets drawn from a given family of sets. It is necessary and sufficient that the family have the following properties: • Every
induced subgraph of a graph in the family must also be in the family. • Every graph formed from a graph in the family by replacing a vertex by a
clique must also belong to the family. • There exists an infinite sequence of graphs in the family, each of which is an induced subgraph of the next graph in the sequence, with the property that every graph in the family is an induced subgraph of a graph in the sequence. If the intersection graph representations have the additional requirement that different vertices must be represented by different sets, then the clique expansion property can be omitted. ==Related concepts==