Document Open Access Logo

Interval-Like Graphs and Digraphs

Authors Pavol Hell, Jing Huang, Ross M. McConnell, Arash Rafiey

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2018.68.pdf
  • Filesize: 394 kB
  • 13 pages

Document Identifiers

Author Details

Pavol Hell
  • School of Computing Science, Simon Fraser University, Burnaby, B.C., Canada V5A 1S6
Jing Huang
  • Mathematics and Statistics, University of Victoria, Victoria, B.C., Canada V8W 2Y2
Ross M. McConnell
  • Computer Science Department, Colorado State University, Fort Collins, CO 80523-1873
Arash Rafiey
  • Mathematics and Computer Science, Indiana State University, Terre Haute, IN 47809

Funding

  • Hell, Pavol: The author was supported by an NSERC (Canada) Discovery Grant

Cite As Get BibTex

Pavol Hell, Jing Huang, Ross M. McConnell, and Arash Rafiey. Interval-Like Graphs and Digraphs. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 68:1-68:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.MFCS.2018.68

Abstract

We unify several seemingly different graph and digraph classes under one umbrella. These classes are all, broadly speaking, different generalizations of interval graphs, and include, in addition to interval graphs, adjusted interval digraphs, threshold graphs, complements of threshold tolerance graphs (known as `co-TT' graphs), bipartite interval containment graphs, bipartite co-circular arc graphs, and two-directional orthogonal ray graphs. (The last three classes coincide, but have been investigated in different contexts.) This common view is made possible by introducing reflexive relationships (loops) into the analysis. We also show that all the above classes are united by a common ordering characterization, the existence of a min ordering. We propose a common generalization of all these graph and digraph classes, namely signed-interval digraphs, and show that they are precisely the digraphs that are characterized by the existence of a min ordering. We also offer an alternative geometric characterization of these digraphs. For most of the above graph and digraph classes, we show that they are exactly those signed-interval digraphs that satisfy a suitable natural restriction on the digraph, like having a loop on every vertex, or having a symmetric edge-set, or being bipartite. For instance, co-TT graphs are precisely those signed-interval digraphs that have each edge symmetric. We also offer some discussion of future work on recognition algorithms and characterizations.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatoric problems
  • Mathematics of computing → Graph theory
Keywords
  • graph theory
  • interval graphs
  • interval bigraphs
  • min ordering
  • co-TT graph

Metrics

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

References

  1. R. P. Anstee and M. Farber. Characterizations of totally balanced matrices. J. Algorithms, 5:215-230, 1984. Google Scholar
  2. V. L. Beresnev and A. I. Davydov. On matrices with connectedness properties. Upravlyaemye Sistemy, 19:3-13, 1979. Google Scholar
  3. K. S. Booth and G. S. Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Computer and System Sci., 13:335-379, 1976. Google Scholar
  4. A. Bulatov, P. Jeavons, and A. Krokhin. Classifying the complexity of constraints using finite algebras. SIAM J. Computing, 34:720-742, 2005. Google Scholar
  5. V. Chvátal and P. L. Hammer. Set-packing and threshold graphs. Technical report, Univ. Waterloo Res. Report, 1973. Google Scholar
  6. D. G. Corneil, S. Olariu, and L. Stewart. The LBFS structure and recognition of interval graphs. SIAM J. Discrete Math., 23:1905-1953, 2009. Google Scholar
  7. P. Damaschke. Forbidden ordered subgraphs. In R. Bodendiek and R. Henn, editors, Topics in Combinatorics and Graph Theory, pages 219-229. Physika-Verlag HD, 1990. Google Scholar
  8. T. Feder and P. Hell. List homomorphisms to reflexive graphs. J. Combinatorial Theory B, 72:236-250, 1998. Google Scholar
  9. T. Feder, P. Hell, and J. Huang. List homomorphisms and circular arc graphs. Combinatorica, 19:487-505, 1999. Google Scholar
  10. T. Feder, P. Hell, J. Huang, and A. Rafiey. Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms. Discrete Applied Mathematics, 160:697-707, 2012. Google Scholar
  11. D. R. Fulkerson and O. A. Gross. Incidence matrices and interval graphs. Pacific J. Math., 15:835-855, 1965. Google Scholar
  12. P. Golovach, P. Heggerness, R. M. McConnell, V. F. dos Santos, J. P. Spinrad, and J. L. Szwarcfiter. On recognition of threshold tolerance graphs and their complements. Discrete Applied Mathematics, 216:171-180, 2017. Google Scholar
  13. M. C. Golumbic. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York, 1980. Google Scholar
  14. M. C. Golumbic, N. L. Weingarten, and V. Limouzy. Co-TT graphs and a characterization of split co-TT graphs. Discrete Applied Mathematics, 165:168-174, 2014. Google Scholar
  15. W. Gutjahr, E. Welzl, , and G. J. Woeginger. Polynomial graph-colourings. Discrete Applied Mathematics, 35:29-45, 1992. Google Scholar
  16. M. Habib, R. McConnell, C. Paul, , and L. Viennot. Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing. Theoretical Computer Science, 234:59-84, 2000. Google Scholar
  17. P. Hell, J. Huang, R. M. McConnell, and J. Lin. Comparability graphs coverable by two cliques, and cocomparability bigraphs. Manuscript, 2018. Google Scholar
  18. P. Hell, M. Mastrolilli, M. M. Nevisi, and A. Rafiey. Approximation of minimum cost homomorphisms. In Algorithms - ESA 2012, volume 7501 of Lecture Notes in Computer Science, pages 587-598. Springer, 2012. Google Scholar
  19. P. Hell, B. Mohar, and A. Rafiey. Orderings without forbidden patterns. In A. S. Schulz and D. Wagner, editors, Algorithms - ESA 2014, volume 8737 of Lecture Notes in Computer Science. Springer, 2014. Google Scholar
  20. P. Hell and J. Nešetřil. Graph Homomorphisms. Wiley, 2004. Google Scholar
  21. P. Hell and A. Rafiey. Bi-arc digraphs and conservative polymorphisms, 2016. URL: http://arxiv.org/abs/arXiv:1608.03368.
  22. J. Huang. Representation characterizations of chordal bipartite graphs. J. Combinatorial Theory B, 96:673-683, 2006. Google Scholar
  23. B. Klintz, R. Rudolf, and G. J. Woeginger. Permuting matrices to avoid forbidden submatrices. Discrete Applied Mathematics, 60:223-248, 1995. Google Scholar
  24. C. G. Lekkerkerker and J. C. Boland. Representation of a finite graph by a set of intervals on the real line. Fundamenta Math., 51:45-64, 1962. Google Scholar
  25. A. Lubiw. Doubly lexical orderings of matrices. SIAM J. Comput., 16:854-879, 1987. Google Scholar
  26. R. M. McConnell. Linear-time recognition of circular-arc graphs. Algorithmica, 37:93-147, 2003. Google Scholar
  27. C. L. Monma, B. Reed, and W. T. Trotter. Threshold tolerance graphs. J. Graph Theory, 12:343-362, 1988. Google Scholar
  28. R. Paige and R. E. Tarjan. Three partition refinement algorithms. SIAM J. Comput., 16:973-989, 1987. Google Scholar
  29. M. Sen, S. Das, A. B. Roy, and D. B. West. Interval digraphs: an analogue of interval graphs. J. Graph Theory, 13:581-592, 1989. Google Scholar
  30. A. M. Shresta, S. Tayu, and S. Ueno. On two-directional orthogonal ray graphs. In Proceedings of 2010 IEEE International Symposium on Circuits and Systems, pages 1807-1810, 2010. Google Scholar
  31. J. Spinrad. Efficient Graph Representations. Fields Institute Monographs, AMS, 2003. 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 About DROPS Imprint Privacy Contact