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

Date: 10. 12. 2012

Source: Graph theory and algorithms seminar

Source: Graph theory and algorithms seminar

Četrtek 13.12.2012 ob 12:15 v predavalnici 3.05 na Jadranski 21

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.