*BibTeX*

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

*BibTeX*

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