Minimal Proper Interval Completions

Abstract

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