Circle graph 2026-10-20
The intersection graph of chords of a circle: each chord is a vertex, and two vertices are adjacent when their chords cross. Two chords with distinct endpoints cross exactly when their endpoints alternate around the circle.
Intersection graph 2026-10-14
An intersection graph has one vertex for each member of a family of sets. Two distinct vertices have an edge exactly when their associated sets have a nonempty intersection. A clique therefore describes pairwise intersections; it need not give a single element common to all those sets.
A clique records pairwise relationships. If vertices represent sets and an edge means a nonempty intersection, a clique does not by itself guarantee an element common to every set. Take
Then , and , so their intersection graph is . But . The graph faithfully records all three pairwise intersections; the stronger claim of a single shared element requires additional hypotheses.
Permutation graph 2026-10-20
The intersection graph of the segments in a permutation diagram. Two segments cross exactly when their endpoint orders disagree. A set of mutually noncrossing segments corresponds to a monotone subsequence of the endpoint permutation.