Chapter 44. Intersection Graphs

An intersection graph represents overlaps among sets or geometric objects. Each object becomes a vertex, and two vertices are adjacent exactly when the corresponding objects intersect.

This construction converts geometric or set-theoretic relationships into graph-theoretic form. Many important graph classes arise this way. Interval graphs, circle graphs, chordal graphs, permutation graphs, and string graphs are all examples of intersection graphs.

Intersection graphs form a bridge between graph theory and geometry. Instead of studying only abstract adjacency, they study adjacency generated by spatial or combinatorial overlap. (en.wikipedia.org)

44.1 Basic Definition

Let

be a family of sets.

The intersection graph of $\mathcal{F}$ is the graph $G$ defined by:

Thus two vertices are adjacent exactly when the corresponding sets intersect.

This definition applies equally to intervals, disks, polygons, curves, subtrees, or arbitrary sets.

44.2 Interval Graphs

An interval graph is the intersection graph of intervals on the real line.

Suppose each vertex corresponds to a closed interval

Two vertices are adjacent when the intervals overlap.

For example,

intersects

so the corresponding vertices are adjacent.

But

does not intersect

so no edge is present.

Interval graphs model scheduling and resource allocation. If intervals represent time periods, then adjacency means overlap in time. Interval graph coloring therefore corresponds to assigning resources to overlapping tasks.

Interval graphs are chordal and have strong algorithmic properties. Many optimization problems that are hard on general graphs become easy on interval graphs. (en.wikipedia.org)

44.3 Unit Interval Graphs

A unit interval graph is an interval graph in which all intervals have equal length.

For example, all intervals may have length $1$:

Unit interval graphs model situations where all objects have the same size or duration.

Although every unit interval graph is an interval graph, the converse is false. Long intervals can overlap many short intervals in ways impossible under equal-length restrictions.

44.4 Circle Graphs

A circle graph is the intersection graph of chords of a circle.

Each vertex corresponds to a chord. Two vertices are adjacent when the corresponding chords cross inside the circle.

Circle graphs arise naturally in combinatorics and topology. They also appear in problems involving crossings and arrangements.

Unlike interval graphs, which are defined on a line, circle graphs use cyclic geometry.

44.5 String Graphs

A string graph is the intersection graph of curves in the plane.

Each vertex corresponds to a curve. Two vertices are adjacent when the curves intersect.

String graphs are very general. Many graph classes can be represented as string graphs.

For example:

The greater generality makes recognition and optimization problems harder.

44.6 Segment Graphs

A segment graph is the intersection graph of straight-line segments in the plane.

Each vertex corresponds to a segment. Two vertices are adjacent when the segments intersect.

Segment graphs lie between geometric graph theory and intersection graph theory. The geometry of the segments determines adjacency.

Not every graph is a segment graph. Determining whether a graph admits such a representation can be difficult.

Segment graphs are important in visibility problems, VLSI design, and computational geometry.

44.7 Disk Graphs

A disk graph is the intersection graph of disks in the plane.

Each vertex corresponds to a disk. Two vertices are adjacent when the disks overlap.

A particularly important special case is the unit disk graph, where all disks have the same radius.

Unit disk graphs model wireless communication networks:

Two devices are adjacent when they are close enough for their ranges to overlap.

Unit disk graphs combine graph structure with Euclidean geometry and distance constraints.

44.8 Intersection Models

A graph may admit many different intersection representations.

For example, a graph may be representable both as:

The representation chosen often determines which structural theorems and algorithms apply.

Intersection models are therefore not merely visualizations. They encode combinatorial structure.

44.9 Recognition Problems

A recognition problem asks whether a given abstract graph belongs to a certain class.

For intersection graphs, the question becomes:

Can this graph be represented as the intersection graph of a specified family of objects?

Examples include:

Some recognition problems are solvable efficiently. Others are computationally difficult.

Interval graph recognition, for example, has efficient algorithms. Recognition of general segment graphs is much harder.

44.10 Clique Interpretation

In an intersection graph, a clique corresponds to a collection of objects that pairwise intersect.

For interval graphs, Helly-type phenomena become important. In intervals on the real line, pairwise intersection implies total intersection:

If every pair of intervals intersects, then all intervals share at least one common point.

Therefore every clique in an interval graph corresponds to a common intersection point.

This property fails for arbitrary geometric objects. Three sets may intersect pairwise without having a common intersection.

44.11 Coloring Interpretation

Coloring an intersection graph often corresponds to separating overlapping objects.

For interval graphs:

A scheduling example illustrates this clearly.

Suppose intervals represent lectures using the same classroom system. Two overlapping lectures cannot use the same room. Coloring the interval graph assigns rooms so that overlapping lectures receive different colors.

Since interval graphs are perfect, the chromatic number equals the clique number. Thus the minimum number of rooms equals the maximum number of simultaneously overlapping lectures.

44.12 Chordal Graphs and Intersection Graphs

A chordal graph is a graph in which every cycle of length at least four has a chord.

Chordal graphs admit a subtree intersection characterization:

A graph is chordal if and only if it is the intersection graph of subtrees of a tree. (en.wikipedia.org)

This theorem is important because it translates a purely graph-theoretic condition into an intersection representation.

Interval graphs appear as the special case where the host tree is a path.

Thus:

This viewpoint unifies several graph classes.

44.13 Comparability with Geometric Graphs

Intersection graphs and geometric graphs are related but distinct.

In a geometric graph, the graph itself is drawn geometrically. In an intersection graph, geometry generates adjacency.

For example, a segment graph is an intersection graph whose objects are line segments. The segments themselves are not edges of the graph. Instead, each segment represents a vertex.

This distinction is important.

44.14 Applications

Intersection graphs appear in many applications.

The general principle is simple:

Objects become vertices, and interaction becomes adjacency.

44.15 Perfect Graphs

Many important intersection graph classes are perfect graphs.

A graph is perfect if, for every induced subgraph,

where

is the clique number.

Interval graphs and chordal graphs are perfect. This makes many optimization problems tractable.

For example:

The structural restrictions imposed by geometric intersection often simplify combinatorial behavior.

44.16 Summary

An intersection graph represents overlaps among sets or geometric objects. Vertices correspond to objects, and adjacency means intersection.

Important classes include:

Intersection graph theory translates geometry into combinatorics. It provides geometric interpretations of adjacency, clique structure, coloring, and optimization. Many classical graph classes can be understood naturally through intersection representations.