Unit interval graphs of open and closed intervals. (English) Zbl 1261.05070
Summary: We give two structural characterizations of the class of finite intersection graphs of the open and closed real intervals of unit length. This class is a proper superclass of the well-known unit interval graphs.
MSC:
| 05C62 | Graph representations (geometric and intersection representations, etc.) |
| 05C90 | Applications of graph theory |
References:
| [1] | K. P.Bogart and D. B.West, A short proof that “proper=unit”, Discrete Math201 (1999), 21-23. · Zbl 0932.05065 |
| [2] | A.Brandstädt, V. B.Le, and J. P.Spinrad, Graph classes: A survey, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1999. · Zbl 0919.05001 |
| [3] | D. G.Corneil, A simple 3‐sweep LBFS algorithm for the recognition of unit interval graphs, Discrete Appl Math138 (2004), 371-379. · Zbl 1042.05067 |
| [4] | D. G.Corneil, H.Kim, S.Natarajan, S.Olariu, and A. P.Sprague, Simple linear time recognition of unit interval graphs, Inf Process Lett55 (1995), 99-104. · Zbl 0875.68690 |
| [5] | D. G.Corneil, S.Olariu, and L.Stewart, The ultimate interval graph recognition algorithm? (Extended abstract), Proceedings of the 9th annual ACM‐SIAM symposium on Discrete algorithms (SODA), 1998, pp. 175-180. · Zbl 0930.68105 |
| [6] | P. C.Fishburn, Interval orders and interval graphs. A study of partially ordered sets. John Wiley & Sons, New York, 1985. · Zbl 0551.06001 |
| [7] | P.Frankl and H.Maehara, Open‐interval graphs versus closed‐interval graphs, Discrete Math63 (1987), 97-100. · Zbl 0608.05068 |
| [8] | P. W.Goldberg, M. C.Golumbic, H.Kaplan, and R.Shamir, Four strikes against physical mapping of DNA, J Comput Biol2 (1995), 139-152. |
| [9] | M. C.Golumbic, Algorithmic graph theory and perfect graphs, vol. 57. Annals of Discrete Mathematics, Amsterdam, The Netherlands, 2004. · Zbl 1050.05002 |
| [10] | P.Hell, R.Shamir, and R.Sharan, A fully dynamic algorithm for recognizing and representing proper interval graphs, SIAM J Comput31 (2001), 289-305. · Zbl 0992.68065 |
| [11] | C. M. Herrerade Figueiredo, J.Meidanis, and C. Picininde Mello, A linear‐time algorithm for proper interval graph recognition, Inf Process Lett56 (1995), 179-184. · Zbl 0875.68696 |
| [12] | H.Kaplan and R.Shamir, Pathwidth, bandwidth, and completion problems to proper interval graphs with small cliques, SIAM J Comput25 (1996), 540-561. · Zbl 0852.68072 |
| [13] | D. G.Kendall, Incidence matrices, interval graphs, and seriation in archaeology, Pacific J Math28 (1969), 565-570. · Zbl 0185.03301 |
| [14] | C. H.Papadimitriou and M.Yannakakis, Scheduling interval‐ordered tasks, SIAM J Comput8 (1979), 405-409. · Zbl 0421.68040 |
| [15] | F. S.Roberts, Indifference graphs, in Proof techniques in graph theory, F.Harary (ed.) (Editor), Academic Press, 1969, pp. 139-146 · Zbl 0193.24205 |
| [16] | S. B.Sadjad and H. Z.Zadeh, Unit interval graphs, properties and algorithms, School of Computer Science, Technical Report, University of Waterloo, February 2004. |
| [17] | A.Tucker, Structure theorems for some classes of circular‐arc graphs, Discrete Math7 (1974), 167-195. · Zbl 0269.05119 |
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.
