Given an arbitrary graph G=(V,E) and an interval graph H=(V,F) with we say that H is an interval completion of G. The graph H is called a minimal interval completion of G if, for any sandwich graph H′ = (V,F′) with , E ⊆ F′ ⊂ F, H′ is not an interval graph. In this paper we give a time algorithm computing a minimal interval completion of an arbitrary graph. The output is an interval model of the completion.
