Intersection Graph - Classes of Intersection Graphs

Classes of Intersection Graphs

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.
• 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.
• 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 (Schaefer 2010).
• 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.