Interval Graphs: Canonical Representations in Logspace
Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky · SIAM Journal on Computing · 2011
We present a logspace algorithm for computing a canonical labeling, in fact, a canonical interval representation, for interval graphs. To achieve this, we compute canonical interval representations of interval hypergraphs. This approach also yields a canonical labeling of convex graphs. As a consequence, the isomorphism and automorphism problems for these graph classes are solvable in logspace. For proper interval graphs we also design logspace algorithms computing their canonical representations by proper and by unit interval systems.