*BibTeX*

@Article{KKLV11intervalgraphs, author = {Johannes Köbler and Sebastian Kuhnert and Bastian Laubner and Oleg Verbitsky}, title = {Interval graphs: Canonical representations in logspace}, journal = {SIAM Journal on Computing}, year = 2011, volume = 40, number = 5, pages = {1292-1315}, issn = {1501-1526}, doi = {10.1137/10080395X}, }

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

*BibTeX*

@Article{KKLV10intervalgraphs, author = {Johannes Köbler and Sebastian Kuhnert and Bastian Laubner and Oleg Verbitsky}, title = {Interval graphs: Canonical representation in logspace}, booktitle = {Proceedings of 37th International Colloquium on Automata, Languages and Programming (ICALP'10)}, year = 2010, year = {2010}, pages = {384-395}, isbn = {978-3-642-14164-5}, doi = {10.1007/978-3-642-14165-2_33}, }

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.