A new representation of proper interval graphs with an application to clique-width

We introduce a new representation of proper interval graphs that can be computed in linear time and stored in O(n) space. This representation is a 2-dimensional vertex partition. It is particularly interesting with respect to clique-width. Based on this representation, we prove new upper bounds on the clique-width of proper interval graphs.