Maria Saumell: Extending Partial Representations of Proper and Unit Interval Graphs

A recently introduced problem of extending partial interval representations asks, for an interval graph with some intervals pre-drawn by the input, whether it is possible to extend this partial representation to the entire graph. In this paper, we give a linear-time algorithm for extending proper interval representations and an almost quadratic-time algorithm for extending unit interval representations.