×

Min-orderable digraphs. (English) Zbl 1450.05036

Summary: 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, complements of threshold tolerance graphs (known as co-TT graphs), bipartite interval containment graphs, bipartite co-circular arc graphs, and two-directional orthogonal ray bigraphs. (The last three classes coincide, but have been investigated in different contexts.) We show that all of the above classes are united by a common ordering characterization, the existence of a min ordering. However, because the presence or absence of reflexive relationships (loops) affects whether a graph or digraph has a min ordering, to obtain this result, we must define the graphs and digraphs to have those loops that are implied by their definitions. These have been largely ignored in previous work. We propose a common generalization of all these graph and digraph classes, namely signed-interval digraphs, characterized by the existence of a compact representation, a signed-interval model, which is a generalization of known representations of the graph classes. We show that the signed-interval digraphs are precisely those digraphs that are characterized by the existence of a min ordering when the loops implied by the model are considered part of the graph. We also offer an alternative geometric characterization of these digraphs. We show that co-TT graphs are the symmetric signed-interval digraphs, the adjusted interval digraphs are the reflexive signed-interval digraphs, and the interval graphs are the intersection of these two classes, namely, the reflexive and symmetric signed-interval digraphs. Similar results hold for bipartite interval containment graphs, bipartite co-circular arc graphs, and two-directional orthogonal ray bigraphs.

MSC:

05C20 Directed graphs (digraphs), tournaments
05C75 Structural characterization of families of graphs
05C62 Graph representations (geometric and intersection representations, etc.)
05C17 Perfect graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R. P. Anstee and M. Farber, Characterizations of totally balanced matrices, J. Algorithms, 5 (1984), pp. 215-230. · Zbl 0551.05026
[2] K. S. Booth and G. S. Lueker, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, J. Comput. System Sci., 13 (1976), pp. 335-379. · Zbl 0367.68034
[3] A. Bulatov, P. Jeavons, and A. Krokhin, Classifying the complexity of constraints using finite algebras, SIAM J. Comput., 34 (2005), pp. 720-742, https://doi.org/10.1137/S0097539700376676. · Zbl 1071.08002
[4] D. G. Corneil, S. Olariu, and L. Stewart, The LBFS structure and recognition of interval graphs, SIAM J. Discrete Math., 23 (2009), pp. 1905-1953, https://doi.org/10.1137/S0895480100373455. · Zbl 1207.05131
[5] V. Chvátal and P. L. Hammer, Set-Packing and Threshold Graphs, University of Waterloo Research Report, CORR 73-21, 1973.
[6] P. Damaschke, Forbidden ordered subgraphs, in Topics in Combinatorics and Graph Theory, Physica, Heidelberg, 1990, pp. 219-229. · Zbl 0736.05065
[7] M. Farber, Characterizations of strongly chordal graphs, Discrete Math., 43 (1983), pp. 173-189. · Zbl 0514.05048
[8] T. Feder and P. Hell, List homomorphisms to reflexive graphs, J. Combin. Theory Ser. B, 72 (1998), pp. 236-250. · Zbl 0904.05078
[9] T. Feder, P. Hell, and J. Huang, List homomorphisms and circular arc graphs, Combinatorica, 19 (1999), pp. 487-505. · Zbl 0985.05048
[10] T. Feder, P. Hell, and J. Huang, Bi-arc graphs and the complexity of list homomorphisms, J. Graph Theory, 42 (2003), pp. 61-80. · Zbl 1057.05033
[11] T. Feder, P. Hell, J. Huang, and A. Rafiey, Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms, Discrete Appl. Math., 160 (2012), pp. 697-707. · Zbl 1236.05092
[12] D. R. Fulkerson and O. A. Gross, Incidence matrices and interval graphs, Pacific J. Math., 15 (1965), pp. 835-855. · Zbl 0132.21001
[13] P. A. Golovach, P. Heggernes, R. M. McConnell, V. F. dos Santos, J. P. Spinrad, and J. L. Szwarcfiter, On recognition of threshold tolerance graphs and their complements, Discrete Appl. Math., 216 (2017), pp. 171-180. · Zbl 1350.05054
[14] M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980. · Zbl 0541.05054
[15] M. C. Golumbic and E. R. Scheinerman, Containment graphs, posets, and related classes of graphs, in Combinatorial Mathematics, G. S. Bloom et al., eds., Ann. New York Acad. Sci. 555, New York Acad. Sci., New York, 1989, pp. 192-204. · Zbl 0738.05067
[16] M. C. Golumbic, N. L. Weingarten, and V. Limouzy, Co-TT graphs and a characterization of split co-TT graphs, Discrete Appl. Math., 165 (2014), pp. 168-174. · Zbl 1408.05112
[17] W. Gutjahr, E. Welzl, and G. J. Woeginger, Polynomial graph-colourings, Discrete Appl. Math., 35 (1992), pp. 29-45. · Zbl 0761.05040
[18] M. Habib, R. M. McConnell, C. Paul, and L. Viennot, Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing, Theoret. Comput. Sci., 234 (2000), pp. 59-84. · Zbl 0945.68189
[19] P. Hell and J. Huang, Interval bigraphs and circular arc graphs, J. Graph Theory, 46 (2004), pp. 313-327. · Zbl 1046.05066
[20] P. Hell, J. Huang, R. M. McConnell, and A. Rafiey, Interval-like graphs and digraphs, in Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, LIPIcs. Leibniz Int. Proc. Inform. 117, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2018, 68.
[21] P. Hell, J. Huang, R. M. McConnell, and J. C.-H. Lin, Comparability and Cocomparability Bigraphs, manuscript, 2018.
[22] P. Hell, B. Mohar, and A. Rafiey, Orderings without forbidden patterns, in Algorithms-ESA 2014, Lecture Notes in Comput. Sci. 8737, A. S. Schulz and D. Wagner, eds., Springer, Berlin, Heidelberg, 2014, pp. 554-565. · Zbl 1425.05134
[23] P. Hell, M. Mastrolilli, M. M. Nevisi, and A. Rafiey, Approximation of minimum cost homomorphisms, ESA, 2012, pp. 587-598. · Zbl 1365.05203
[24] P. Hell and J. Nešetřil, Graph Homomorphisms, Oxford Lecture Ser. Math. Appl. 28, Oxford University Press, Oxford, 2004. · Zbl 1062.05139
[25] P. Hell, A. Rafiey, and A. Rafiey, Bi-arc Digraphs and Conservative Polymorphisms, preprint, https://arxiv.org/abs/1608.03368, 2019. · Zbl 1261.05034
[26] J. Huang, Representation characterizations of chordal bipartite graphs, J. Combin. Theory Ser. B, 96 (2006), pp. 673-683. · Zbl 1095.05031
[27] B. Klintz, R. Rudolf, and G. J. Woeginger, Permuting matrices to avoid forbidden submatrices, Discrete Appl. Math., 60 (1995), pp. 223-248. · Zbl 0837.05031
[28] C. G. Lekkerkerker and J. C. Boland, Representation of a finite graph by a set of intervals on the real line, Fund. Math., 51 (1962), pp. 45-64. · Zbl 0105.17501
[29] A. Lubiw, Doubly lexical orderings of matrices, SIAM J. Comput., 16 (1987), pp. 854-879, https://doi.org/10.1137/0216057. · Zbl 0622.05045
[30] R. M. McConnell, Linear-time recognition of circular-arc graphs, Algorithmica, 37 (2003), pp. 93-147. · Zbl 1060.68088
[31] C. L. Monma, B. Reed, and W. T. Trotter, Threshold tolerance graphs, J. Graph Theory, 12 (1988), pp. 343-362. · Zbl 0652.05059
[32] A. M. Shresta, S. Tayu, and S. Ueno, On two-directional orthogonal ray graphs, in Proceedings of the 2010 IEEE International Symposium on Circuits and Systems, IEEE, pp. 1807-1810.
[33] M. Sen, S. Das, A. B. Roy, and D. B. West, Interval digraphs: An analogue of interval graphs, J. Graph Theory, 13 (1989), pp. 581-592. · Zbl 0671.05039
[34] J. P. Spinrad, Efficient Graph Representations, Fields Inst. Monogr. 19, AMS, Providence, RI, 2003. · Zbl 1033.05001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.