Chapter 44. Intersection Graphs
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.
44.1 Basic Definition
Let
$$ \mathcal{F} = {S_1,S_2,\ldots,S_n} $$
be a family of sets.
The intersection graph of (\mathcal{F}) is the graph (G) defined by:
| Object | Meaning |
|---|---|
| Vertex (v_i) | Set (S_i) |
| Edge (v_iv_j) | (S_i \cap S_j \neq \varnothing) |
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
$$ [a_i,b_i]. $$
Two vertices are adjacent when the intervals overlap.
For example,
$$ [1,4] $$
intersects
$$ [3,7], $$
so the corresponding vertices are adjacent.
But
$$ [1,2] $$
does not intersect
$$ [4,5], $$
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.
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):
$$ [a_i,a_i+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:
| Graph class | Representation |
|---|---|
| Interval graph | Intervals on a line |
| Circle graph | Chords of a circle |
| Segment graph | Straight-line segments |
| String graph | Arbitrary curves |
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:
| Geometric object | Interpretation |
|---|---|
| Disk | Communication range of a device |
| Intersection | Devices can communicate |
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:
| Representation | Objects |
|---|---|
| Interval graph | Intervals |
| Chordal graph | Subtrees of a tree |
| String graph | Curves in the plane |
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:
| Class | Recognition question |
|---|---|
| Interval graph | Can the graph be represented by intervals? |
| Circle graph | Can the graph be represented by chords? |
| Unit disk graph | Can the graph be represented by equal-radius disks? |
| Segment graph | Can the graph be represented by segments? |
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:
| Graph concept | Geometric meaning |
|---|---|
| Vertex coloring | Assign resources to intervals |
| Adjacent vertices | Overlapping intervals |
| Chromatic number | Minimum number of simultaneous resources |
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.
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:
| Graph class | Representation |
|---|---|
| Interval graph | Intervals on a line |
| Chordal graph | Subtrees of a tree |
This viewpoint unifies several graph classes.
44.13 Comparability with Geometric Graphs
Intersection graphs and geometric graphs are related but distinct.
| Type | Main idea |
|---|---|
| Geometric graph | Vertices are points, edges are geometric segments |
| Intersection graph | Vertices represent geometric objects |
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.
| Area | Interpretation |
|---|---|
| Scheduling | Overlapping time intervals |
| Biology | Interacting genomic intervals |
| Wireless networks | Overlapping transmission regions |
| Computer graphics | Visibility overlap |
| Database systems | Overlapping ranges |
| VLSI design | Intersecting circuit components |
| Computational geometry | Spatial overlap relations |
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,
$$ \chi(G) = \omega(G), $$
where
$$ \omega(G) $$
is the clique number.
Interval graphs and chordal graphs are perfect. This makes many optimization problems tractable.
For example:
| Problem | General graphs | Interval graphs |
|---|---|---|
| Coloring | NP-hard | Efficient |
| Maximum clique | NP-hard | Efficient |
| Maximum independent set | NP-hard | Efficient |
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:
| Graph class | Objects |
|---|---|
| Interval graph | Intervals |
| Circle graph | Chords of a circle |
| Segment graph | Line segments |
| Disk graph | Disks |
| String graph | Curves |
| Chordal graph | Subtrees of a tree |
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.