Interval graphs: Canonical representations in logspace.
With Johannes Köbler, Bastian Laubner, Oleg Verbitsky.
SIAM Journal on Computing 40(5):1292–1315 (2011).

Abstract. 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.

Conference version:
Interval graphs: Canonical representation in logspace
With Johannes Köbler, Bastian Laubner, Oleg Verbitsky.
Automata, Languages and Programming (Proceedings of 37th ICALP). Springer, 2010. Pp 384–395.