Short models for unit interval graphs

MIN CHIH LIN; FRANCISCO J. SOULIGNAC; JAYME L. SZWARCFITER

Electronic Notes in Discrete Mathematics

Elsevier

Lugar: Amsterdam; Año: 2009 vol. 35 p. 247 - 255

1571-0653

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(n^2), solving a problem posed by Gardi (Discrete Math., 307 (22), 2906-2908, 2007).