×

Recognition and characterization of chronological interval digraphs. (English) Zbl 1295.05161

Summary: Interval graphs admit elegant structural characterizations and linear time recognition algorithms; on the other hand, the usual interval digraphs lack a forbidden structure characterization as well as a low-degree polynomial time recognition algorithm. In this paper we identify another natural digraph analogue of interval graphs that we call “chronological interval digraphs”. By contrast, the new class admits both a forbidden structure characterization and a linear time recognition algorithm. Chronological interval digraphs arise by interpreting the standard definition of an interval graph with a natural orientation of its edges. Specifically, \(G\) is a chronological interval digraph if there exists a family of closed intervals \(I_v\), \(v \in V(G)\), such that \(uv\) is an arc of \(G\) if and only if \(I_u\) intersects \(I_v\) and the left endpoint of \(I_u\) is not greater than the left endpoint of \(I_v\). (Equivalently, if and only if \(I_u\) contains the left endpoint of \(I_v\).) We characterize chronological interval digraphs in terms of vertex orderings, in terms of forbidden substructures, and in terms of a novel structure of so-called \(Q\)-paths. The first two characterizations exhibit strong similarity with the corresponding characterizations of interval graphs. The last characterization leads to a linear time recognition algorithm.

MSC:

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

References:

[1] J. Bang-Jensen, J. Huang and E. Prisner, In-tournament digraphs, J. Combinatorial Theory B 59 (1993) 267 - 287. the electronic journal of combinatorics 20(3) (2013), #P512 · Zbl 0794.05033
[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) 335 - 379. · Zbl 0367.68034
[3] D.E. Brown, A.H. Busch, and J.R. Lundgren, Interval tournaments, J. Graph Theory 56 (2007) 72 - 81. · Zbl 1130.05028
[4] D.G. Corneil, S. Olariu, and L. Stewart, The LBFS structure and the recognition of interval graphs, SIAM J. Discrete Math., 23 (2009) 1905 - 1953. · Zbl 1207.05131
[5] S. Das and M. Sen, An interval digraph in relation to its associated bipartite graph, Discrete Math. 122 (1993) 113 - 136. · Zbl 0792.05060
[6] S. Das, P. Talukdar, M. Sen, Homogeneously representable interval digraphs, Electronic Notes in Discrete Math. 15 (2003) 75 - 87. · Zbl 1259.05142
[7] T. Feder, P. Hell, J. Huang, and A. Rafiey, Adjusted interval digraphs, Electronic Notes in Discrete Math. 32 (2009) 83 - 91. · Zbl 1267.05257
[8] T. Feder, P. Hell, J. Huang, and A. Rafiey, Interval graphs, adjusted interval digraphs and reflexive list homomorphisms, Discrete Applied Mathematics 160 (2012) 697 707. · Zbl 1236.05092
[9] D.R. Fulkerson and O.A. Gross, Incidence matrices and interval graphs, Pacific J. Math. 15 (1965) 835 - 855. · Zbl 0132.21001
[10] P.C. Gilmore and A.J. Hoffman, A characterization of comparability graphs and interval graphs, Canadian J. Math. 16 (1964) 539 - 548. · Zbl 0121.26003
[11] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980. · Zbl 0541.05054
[12] J. Huang, Representation characterizations of chordal bipartite graphs, J. Combinatorial Theory B 96 (2006) 673 - 683. · Zbl 1095.05031
[13] C.G. Lekkerkerker and J.C. Boland, Representation of a finite graph by a set of intervals on the real line, Fundamenta Math. 51 (1962) 45 - 64. · Zbl 0105.17501
[14] F.R. McMorris and H.M. Mulder, Subpath acyclic digraphs, Discrete Math. 154 (1996) 189 - 201. · Zbl 0851.05054
[15] H. M¨uller, Recognizing interval digraphs and interval bigraphs in polynomial time, Discrete Appl. Math. 78 (1997) 189 - 205. · Zbl 0890.68103
[16] E. Prisner, A characterization of interval catch digraphs, Discrete Math. 73 (1989) 285 - 289. · Zbl 0669.05038
[17] M. Sen, S. Das, A.B. Roy and D.B. West, Interval digraphs: An analogue of interval graphs, J. Graph Theory 13 (1989) 581 - 592. · Zbl 0671.05039
[18] M. Sen, B.K. Sanyal and D.B. West, Representing digraphs using intervals and circular arcs, Discrete Math. 147 (1995) 235 - 235. · Zbl 0838.05056
[19] M. Sen, P. Talukdar and S. Das, Chronological orderings of interval digraphs, Discrete Math. 306 (2006) 1601 - 1609. the electronic journal of combinatorics 20(3) (2013), #P513 · Zbl 1093.05027
[20] D. Skrien, Chronological orderings of interval graphs, Discrete Applied Math. 8 (1984) 69 - 83. · Zbl 0543.05059
[21] R.E. Tarjan, Depth-first search and linear graph algorithms, 12th Annual Symposium on Switching and Automata Theory (SWAT 1971), pp.114 - 121. · Zbl 0251.05107
[22] D.B. West, Short proofs for interval digraphs, Discrete Math. 178 (1998) 287 - 292. · Zbl 0884.05044
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.