Document Open Access Logo

On the Classes of Interval Graphs of Limited Nesting and Count of Lengths

Authors Pavel Klavík, Yota Otachi, Jiri Šejnoha

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2016.45.pdf
  • Filesize: 0.52 MB
  • 13 pages

Document Identifiers

Author Details

Pavel Klavík
Yota Otachi
Jiri Šejnoha

Cite AsGet BibTex

Pavel Klavík, Yota Otachi, and Jiri Šejnoha. On the Classes of Interval Graphs of Limited Nesting and Count of Lengths. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 45:1-45:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ISAAC.2016.45

Abstract

In 1969, Roberts introduced proper and unit interval graphs and proved that these classes are equal. Natural generalizations of unit interval graphs called k-length interval graphs were considered in which the number of different lengths of intervals is limited by k. Even after decades of research, no insight into their structure is known and the complexity of recognition is open even for k = 2. We propose generalizations of proper interval graphs called k-nested interval graphs in which there are no chains of k + 1 intervals nested in each other. It is easy to see that k-nested interval graphs are a superclass of k-length interval graphs. We give a linear-time recognition algorithm for k-nested interval graphs. This algorithm adds a missing piece to Gajarský et al. [FOCS 2015] to show that testing FO properties on interval graphs is FPT with respect to the nesting k and the length of the formula, while the problem is W[2]-hard when parameterized just by the length of the formula. Further, we show that a generalization of recognition called partial representation extension is polynomial-time solvable for k-nested interval graphs, while it is NP-hard for k-length interval graphs, even when k = 2.
Keywords
  • interval graphs
  • proper and unit interval graphs
  • recognition
  • partial representation extension

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. P. Angelini, G. Di Battista, F. Frati, V. Jelínek, J. Kratochvíl, M. Patrignani, and I. Rutter. Testing planarity of partially embedded graphs. ACM Trans. Algor., 11(4):32:1-32:42, 2015. Google Scholar
  2. M. Balko, P. Klavík, and Y. Otachi. Bounded representations of interval and proper interval graphs. In ISAAC, volume 8283 of LNCS, pages 535-546. Springer, 2013. Google Scholar
  3. T. Bläsius and I. Rutter. Simultaneous pq-ordering with applications to constrained embedding problems. ACM Trans. Algor., 12(2):16, 2016. Google Scholar
  4. K. S. Booth and G. S. Lueker. Testing for the consecutive ones property, interval graphs, and planarity using PQ-tree algorithms. J. Comput. System Sci., 13:335-379, 1976. Google Scholar
  5. M. R. Cerioli, F. de S. Oliveira, and J. L. Szwarcfiter. On counting interval lengths of interval graphs. Discrete Applied Mathematics, 159(7):532-543, 2011. Google Scholar
  6. S. Chaplick, P. Dorbec, J. Kratochvíl, M. Montassier, and J. Stacho. Contact representations of planar graphs: Extending a partial representation is hard. In WG'14, volume 8747 of LNCS, pages 139-151. Springer, 2014. Google Scholar
  7. S. Chaplick, R. Fulek, and P. Klavík. Extending partial representations of circle graphs. In Graph Drawing, volume 8242 of LNCS, pages 131-142. Springer, 2013. Google Scholar
  8. P. C. Fishburn. Paradoxes of two-length interval orders. Discrete Math., 52(2):165-175, 1984. Google Scholar
  9. P. C. Fishburn. Interval graphs and interval orders. Discrete Math., 55(2):135-149, 1985. Google Scholar
  10. P. C. Fishburn. Interval orders and interval graphs: A study of partially ordered sets. John Wiley &Sons, 1985. Google Scholar
  11. D. R. Fulkerson and O. A. Gross. Incidence matrices and interval graphs. Pac. J. Math., 15:835-855, 1965. Google Scholar
  12. J. Gajarský, D. Lokshtanov, J. Obdržálek, S. Ordyniak, M. S. Ramanujan, and S. Saurabh. FO model checking on posets of bounded width. In FOCS 2015, pages 963-974, 2015. Google Scholar
  13. R. Ganian, P. Hlinený, D. Král, J. Obdržálek, J. Schwartz, and J. Teska. FO model checking of interval graphs. Logical Methods in Computer Science, 11(4:11):1-20, 2015. Google Scholar
  14. F. Joos, C. Löwenstein, F. de S. Oliveira, D. Rautenbach, and J. L. Szwarcfiter. Graphs of interval count two with a given partition. Inform. Process. Lett., 114(10):542-546, 2014. Google Scholar
  15. P. Klavík, J. Kratochvíl, T. Krawczyk, and B. Walczak. Extending partial representations of function graphs and permutation graphs. In ESA, volume 7501 of LNCS, pages 671-682. Springer, 2012. Google Scholar
  16. P. Klavík, J. Kratochvíl, Y. Otachi, I. Rutter, T. Saitoh, M. Saumell, and T. Vyskočil. Extending partial representations of proper and unit interval graphs. Algorithmica, 2016. Google Scholar
  17. P. Klavík, J. Kratochvíl, Y. Otachi, and T. Saitoh. Extending partial representations of subclasses of chordal graphs. Theoretical Computer Science, 576:85-101, 2015. Google Scholar
  18. P. Klavík, J. Kratochvíl, Y. Otachi, T. Saitoh, and T. Vyskočil. Extending partial representations of interval graphs. Algorithmica, 2016. Google Scholar
  19. P. Klavík, J. Kratochvíl, and T. Vyskočil. Extending partial representations of interval graphs. In TAMC, volume 6648 of LNCS, pages 276-285. Springer, 2011. Google Scholar
  20. P. Klavík, Y. Otachi, and J. Šejnoha. On the classes of interval graphs of limited nesting and count of lengths. CoRR, abs/1510.03998, 2015. Google Scholar
  21. P. Klavík and M. Saumell. Minimal obstructions for partial representation extension of interval graphs. In ISAAC, volume 8889 of LNCS, pages 401-413, 2014. Google Scholar
  22. N. Korte and R. Möhring. An incremental linear-time algorithm for recognizing interval graphs. SIAM J. Comput., 18(1):68-81, 1989. Google Scholar
  23. R. Leibowitz, S. F. Assmann, and G. W. Peck. The interval count of a graph. SIAM J. Algebr. Discrete Methods, 3:485-494, 1982. Google Scholar
  24. C. Lekkerkerker and D. Boland. Representation of finite graphs by a set of intervals on the real line. Fund. Math., 51:45-64, 1962. Google Scholar
  25. M. Patrignani. On extending a partial straight-line drawing. International Journal of Foundations of Computer Science, 17(05):1061-1069, 2006. Google Scholar
  26. A. Proskurowski and J. A. Telle. Classes of graphs with restricted interval models. Discrete Mathematics &Theoretical Computer Science, 3(4):167-176, 1999. Google Scholar
  27. F. S. Roberts. Indifference graphs. Proof techniques in graph theory, pages 139-146, 1969. Google Scholar
  28. D. J. Rose, R. E. Tarjan, and G. S. Lueker. Algorithmic aspects of vertex elimination on graphs. SICOMP, 5(2):266-283, 1976. Google Scholar
  29. D. Skrien. Chronological orderings of interval graphs. Discrete Appl. Math., 8(1):69-83, 1984. Google Scholar
  30. F. J. Soulignac. Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. CoRR, abs/1408.3443, 2014. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact