Short Models for Unit Interval Graphs

We present one more proof of the fact that the class of proper interval graphs is precisely the class of unit interval graphs. The proof leads to a new and efficient O(n) time and space algorithm that transforms a proper interval model of the graph into a unit model, where all the extremes are integers in the range 0 to O(n2), solving a problem posed by Gardi (Discrete Math., 307 (22), 2906–2908, 2007).