Interval Graphs, in depth: three characterisations, certifying recognition, linear sweeps and the endpoint convention trap

Definition and the endpoint convention

Formally, G is an interval graph if there is a family of intervals I(v) on the real line, one per vertex, such that u and v are adjacent exactly when I(u) and I(v) intersect. That family is an interval model (or representation) of G. Models are not unique: stretching the line, or shifting endpoints that do not cross any other endpoint, gives the same graph.

One convention must be fixed before anything else: are intervals closed, [l, r], or half-open, [l, r)? For closed intervals, [6, 8] and [8, 11] touch at 8 and intersect. For half-open, [6, 8) and [8, 11) do not. Both conventions produce exactly the same class of graphs, because any finite model in one can be perturbed into the other, but a given list of numbers produces different graphs under the two. Calendar and booking systems usually want half-open, because a meeting that ends at 10:00 does not clash with one that starts at 10:00. Graph theory texts usually use closed. This page uses closed intervals throughout and shows the difference in the worked example.

Three characterisations

Three classical theorems characterise interval graphs without mentioning intervals, and each one gives a different handle on recognition.

• Lekkerkerker and Boland (1962). G is an interval graph if and only if it is chordal and has no asteroidal triple. An asteroidal triple is three vertices such that each pair is joined by a path avoiding the closed neighbourhood of the third. Intervals cannot do this: of any three pairwise non-adjacent intervals, one lies between the other two, and every path between the outer two must pass through its neighbourhood.
• Gilmore and Hoffman (1964). G is an interval graph if and only if it is chordal and its complement is a comparability graph, meaning the non-edges can be oriented transitively. The orientation is simply left of: I(u) entirely left of I(v).
• Fulkerson and Gross (1965). G is an interval graph if and only if its maximal cliques can be arranged in a sequence so that, for every vertex, the cliques containing it are consecutive. Such a sequence is a clique path. Equivalently, the vertex-by-clique incidence matrix has the consecutive-ones property for columns ordered this way.

The third theorem is the constructive one. Given a clique path C1, ..., Ck, set I(v) = [first index of a clique containing v, last index]. Two vertices share a clique exactly when they are adjacent, and their index ranges overlap exactly when they share a clique, so this is a model. Each maximal clique of an interval graph corresponds to a point where all its intervals overlap, which is why an interval graph on n vertices has at most n maximal cliques.

The smallest chordal graph that is not an interval graph is worth memorising. Take a centre x with three neighbours y1, y2, y3, and give each yi its own leaf zi. That tree, the subdivided claw, is chordal (all trees are), but z1, z2, z3 form an asteroidal triple: the path z1 y1 x y2 z2 avoids the neighbourhood of z3, and symmetrically for the others. No interval model exists. If you need a quick sanity check of a recognition routine, this graph and C4 (not chordal) are the first two negative tests.

Recognition, and why it should certify

Recognition means: given only the graph, decide whether it is an interval graph and, if so, produce a model. Booth and Lueker gave the first linear-time algorithm in 1976. It finds the maximal cliques using a perfect elimination ordering (the machinery in the chordal graphs article) and then tests the consecutive-ones property with a PQ-tree, a data structure that represents every clique order consistent with the constraints seen so far. PQ-trees are correct and fast but notoriously fiddly to implement. Later algorithms avoid them: Habib, McConnell, Paul and Viennot (2000) used Lexicographic Breadth-First Search with partition refinement, and Corneil, Olariu and Stewart (2009) gave a recognition algorithm built from a sequence of LexBFS sweeps, each starting where the previous one ended. Both run in O(n + m).

For a production system the important design choice is not which algorithm, but that the output is certifying. A yes answer should come with a model you can check independently. A no answer should come with an obstruction: an induced cycle of length four or more, or an asteroidal triple. Checking a model is easy and fast; trusting a bare boolean from a complex routine is not. When you only need small graphs, for tests or for configuration validation, a brute-force recogniser over clique orders is a fine oracle:

from itertools import permutations

def model_matches(adj, model):
    # adj: dict vertex -> set of neighbours; model: dict vertex -> (l, r), closed intervals
    vs = list(adj)
    for i, u in enumerate(vs):
        for v in vs[i + 1:]:
            meet = model[u][0] <= model[v][1] and model[v][0] <= model[u][1]
            if meet != (v in adj[u]):
                return False
    return True

def maximal_cliques(adj):                 # Bron-Kerbosch with pivot; fine for small graphs
    out = []
    def bk(r, p, x):
        if not p and not x:
            out.append(frozenset(r)); return
        pivot = max(p | x, key=lambda w: len(adj[w] & p))
        for v in list(p - adj[pivot]):
            bk(r | {v}, p & adj[v], x & adj[v]); p = p - {v}; x = x | {v}
    bk(set(), set(adj), set())
    return out

def brute_force_model(adj):
    # Fulkerson-Gross: try every clique order; return a certified model or None
    cliques = maximal_cliques(adj)
    for order in permutations(cliques):
        model = {}
        for v in adj:
            idx = [i for i, c in enumerate(order) if v in c]
            if idx and idx[-1] - idx[0] + 1 != len(idx):
                break                     # cliques containing v are not consecutive
            model[v] = (idx[0], idx[-1]) if idx else (len(order), len(order))
        else:
            if model_matches(adj, model):
                return model
    return None

The brute force is factorial in the number of maximal cliques, so keep it to about eight cliques and use it to cross-check a fast implementation on many random small graphs.

Sweeps that solve the hard problems

Once you have a model, every classic optimisation problem is a sweep over sorted endpoints. Interval graphs are perfect, which is why these greedy answers are exactly optimal rather than approximations: see perfect graphs for the theory.

import heapq

def sweep(model):
    # model: dict name -> (l, r), closed intervals. Starts sort before ends at equal
    # coordinates, so touching intervals overlap. For half-open, sort ends first.
    events = sorted([(l, 0, v) for v, (l, r) in model.items()] +
                    [(r, 1, v) for v, (l, r) in model.items()])
    active, cliques, last_was_start = set(), [], False
    colour, free, next_colour = {}, [], 0
    for x, kind, v in events:
        if kind == 0:
            active.add(v)
            if free:
                colour[v] = heapq.heappop(free)
            else:
                colour[v] = next_colour; next_colour += 1
            last_was_start = True
        else:
            if last_was_start:
                cliques.append(sorted(active))   # a start-to-end transition: maximal
            active.discard(v)
            heapq.heappush(free, colour[v])
            last_was_start = False
    return cliques, colour, next_colour

def max_independent_set(model):
    chosen, last_end = [], float("-inf")
    for v, (l, r) in sorted(model.items(), key=lambda kv: kv[1][1]):
        if l > last_end:                     # strict: closed intervals that touch overlap
            chosen.append(v); last_end = r
    return chosen

Two details in that code are the whole difference between right and wrong. The event sort puts starts before ends at the same coordinate, which is what closed intervals require; flip it for half-open. And the independent-set test uses a strict comparison for the same reason. The activity selection article proves the earliest-finish rule in detail, and graph colouring shows why the same greedy fails on general graphs.

Worked example: seven intervals, two conventions

Seven closed intervals: a [0, 4], b [1, 3], c [2, 7], d [5, 9], e [6, 8], f [8, 11], g [10, 12]. The graph has nine edges: ab, ac, bc, cd, ce, de, df, ef, fg.

Running the sweep emits maximal cliques {a, b, c}, {c, d, e}, {d, e, f} and {f, g}, in that order. That order is a Fulkerson-Gross clique path: c appears in the first two, d and e in the middle two, f in the last two, and every other vertex in one. The maximum clique has size 3, and the sweep colours a, d, g with 0, b, e with 1 and c, f with 2, three colours, matching the clique. The earliest-finish rule picks b [1, 3], then e [6, 8], then g [10, 12]; f is skipped because it starts at 8, which a closed e still covers. Three independent vertices, and three cliques ({a, b, c}, {d, e, f}, {g}) cover every vertex, so both are optimal.

Now reread the same numbers as half-open intervals. e [6, 8) and f [8, 11) no longer meet, so the edge ef disappears and the graph has eight edges. The maximal cliques become {a, b, c}, {c, d, e}, {d, f} and {f, g}. The colouring still needs three colours, but the independent set can now take f instead of g. Two services reading one interval table with different conventions will disagree about conflicts, and neither will report an error.

Proper and unit interval graphs

A proper interval graph has a model in which no interval properly contains another. A unit interval graph has a model in which all intervals have the same length. Roberts proved in 1969 that these are the same class, and that it is exactly the interval graphs with no induced claw (one vertex adjacent to three pairwise non-adjacent vertices). The model in the worked example is not proper, because a [0, 4] contains b [1, 3] and c [2, 7] contains e [6, 8]. The graph is still a proper interval graph: no vertex has three pairwise non-adjacent neighbours (c's neighbours a, b, d, e contain two edges), so by Roberts' theorem some other model with no nesting exists. Properness belongs to the graph; nesting belongs to one model.

Proper interval graphs model uniform-duration jobs, fixed-width windows and equal-length sequencing reads, and they admit a vertex ordering in which every closed neighbourhood is a contiguous block, found in linear time with LexBFS.

Where interval graphs appear

• Register allocation. In straight-line code, live ranges are intervals, so sweep colouring is optimal; that is the intuition behind linear scan. With branches and loops, live ranges stop being single intervals and linear scan becomes a heuristic.
• Genome mapping. Seymour Benzer asked in 1959 whether overlapping mutations in a gene fit a linear structure, an interval recognition question.
• Reservation systems. Rooms, machines and GPU time slots are resources; bookings are intervals. Maximum clique is peak demand; colouring is an assignment.
• Query engines. Temporal joins, overlap queries and range indexes are interval problems; interval trees answer stabbing queries when the set changes.

Failure modes

• Mixed endpoint conventions. The worked example shows the effect. Fix the convention in the data type, not in comments.
• Floating-point endpoints. Equal computed times can differ in the last bit and remove an edge. Use integer ticks.
• Materialising the graph. An interval graph can have about n squared over two edges. Work on the sorted model; build adjacency only if you must.
• Assuming the class. Feeding a general graph to an interval-graph routine produces confident nonsense. Recognise first, or verify the model you were given with model_matches.
• Non-certifying recognisers. A PQ-tree bug returns a wrong yes with no way to tell. Always verify the produced model against the input graph.

What to do next

1. Pick an endpoint convention for your data and encode it in the interval type.
2. Implement the sweep and the independent-set function above and reproduce the worked example under both conventions.
3. Write model_matches and use it to verify every model you produce or receive.
4. Build the brute-force recogniser and test it on the subdivided claw, C4 and a few random interval graphs.
5. If you need recognition at scale, implement or adopt a LexBFS-based algorithm and cross-check it against the brute force on small random graphs.
6. Check whether your data is proper (claw-free); if so, use the simpler ordering.