We present a logspace algorithm for computing a canonical interval representation and a canonical labeling of interval graphs. As a consequence, the isomorphism and automorphism problems for interval graphs are solvable in logspace.

more >>>

We consider the problem of finding interval representations of graphs that additionally respect given interval lengths and/or pairwise intersection lengths, which are represented as weight functions on the vertices and edges, respectively. Pe'er and Shamir proved that the problem is NP-complete if only the former are given [SIAM J. Discr. ... more >>>