Computing the clique-separator graph for an interval graph in linear time

We present an algorithm to compute the clique-separator graph of an interval graph in O(m+n) time. This improves the running time of O(n2) given in [11]. The algorithm is simple and uses no complicated data structures.