Interval graph representation with given interval and intersection lengths

We consider the problem of finding interval graph representations 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 (1997 [25]) proved that the problem is NPNP-complete if only the former are given. For the case when both are given, Fulkerson and Gross (1965 [8]) gave an O(n2)O(n2) time algorithm; we improve this to O(n+m)O(n+m) time and supplement it with a logspace algorithm. For the case when only the latter are given, we give both an O(nm)O(nm) time algorithm and a logspace algorithm. In all these bounds, n is the number of vertices and m is the number of edges in the input graph.Complementing their hardness result, Pe'er and Shamir give a polynomial-time algorithm for the case that the input graph has a unique interval ordering of its maximal cliques. For such graphs, their algorithm computes an interval representation (if it exists) that respects a given set of distance inequalities between the interval endpoints. We observe that deciding if such a representation exists is NLNL-complete.