Abstrakt
Interval graphs are intersection graphs of closed intervals. A generalization of recognition called partial representation extension was introduced recently.
The input gives an interval graph with a partial representation specifying some pre-drawn intervals. We ask whether the remaining intervals can be added to create an extending representation.
In this paper, we characterize the minimal obstructions which make a partial representation non-extendible. This generalizes Lekkerkerker and Boland's characterization of minimal forbidden induced subgraphs of interval graphs.
Each minimal obstruction consists of a forbidden induced subgraph together with at most four pre-drawn intervals. A Helly-type result follows: A partial representation is extendible if and only if every quadruple of pre-drawn intervals is extendible by itself.
Our characterization leads to the first polynomial-time certifying algorithm for partial representation extension of intersection graphs.