@Article{KKW15intervalintersections,
  author =       {Johannes Köbler and Sebastian Kuhnert and
                  Osamu Watanabe},
  title =        {Interval graph representation with given interval and
                  intersection lengths},
  journal =      {Journal of Discrete Algorithms},
  year =         2015,
  volume =       34,
  month =        9,
  pages =        {108-117},
  issn =         {1570-8667},
  doi =          {10.1016/j.jda.2015.05.011},
}

Interval graph representation with given interval and intersection lengths.
With Johannes Köbler, Osamu Watanabe.
Journal of Discrete Algorithms 34:108–117 (Sep. 2015).

Abstract.

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. Math. 10.4, 1997]. We give both a linear-time and a logspace algorithm for the case when both are given, and both an O(n⋅m) time and a logspace algorithm when only the latter are given. We also show that the resulting interval systems are unique up to isomorphism.
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 maxcliques. For such graphs, their algorithm computes an interval representation that respects a given set of distance inequalities between the interval endpoints (if it exists). We observe that deciding if such a representation exists is NL-complete.

@InProceedings{KKW12intervalintersections,
    author =       {Johannes Köbler and Sebastian Kuhnert and
                    Osamu Watanabe},
    title =        {Interval graph representation with given interval and
                    intersection lengths},
    editor =       {Kun-Mao Chao and Tsan-sheng Hsu and Der-Tsai Lee},
    booktitle =    {Algorithms and Computation (Proceedings of 23rd ISAAC)},
    year =         2012,
    series =       {LNCS},
    number =       7676,
    publisher =    {Springer},
    address =      {Berlin},
    isbn =         {978-3-642-35260-7},
    doi =          {10.1007/978-3-642-35261-4_54},
    pages =        {517-526},
}

Conference version:
Interval graph representation with given interval and intersection lengths
With Johannes Köbler, Osamu Watanabe.
Algorithms and Computation (Proceedings of 23rd ISAAC). Springer, 2012. Pp. 517–526.