On Orders and Interval Graphs

• Márcia R. Cerioli UFRJ
• Fabiano de S. Oliveira UFRJ
• Jayme L. Szwarcfiter UFRJ

Abstract

The thesis summarized in this work has as focus the study of structural properties of interval graphs and orders and the complexity of recognizing them. In particular, (i) we provide characterizations of extreme cliques and homogeneously-clique representable graphs; (ii) we introduce a new order dimension named linear-interval dimension, showing the close existing relation to the recognition problem of PI graphs; (iii) we provide the state-of-the-art knowledge about the interval count problem, presenting the known results in literature; and (iv) we provide efficient algorithms for the computation of the interval count of generalizations of threshold graphs.

References

Cerioli, M. R., Oliveira, F. d. S., and Szwarcfiter, J. L. (2008). Linear-interval dimension and pi orders. Electronic Notes in Discrete Mathematics, 30:111–116.

Cerioli,M. R., Oliveira, F. d. S., and Szwarcfiter, J. L. (2010a). Extreme cliques in interval graphs. Ars Combinatoria, 94:103–114.

Cerioli,M. R., Oliveira, F. d. S., and Szwarcfiter, J. L. (2010b). On representing an interval graph using the minimum number of interval lengths. Matemática Contemporânea, 39:59–67.

Cerioli, M. R., Oliveira, F. d. S., and Szwarcfiter, J. L. (2011). On counting interval lengths of interval graphs. Discrete Applied Mathematics, 159(7):532–543.

Fishburn, P. C. (1985). Interval Orders and Interval Graphs. John Wiley & Sons.

Golumbic, M. and Trenk, A. (2003). Tolerance Graphs. Cambridge University Press.

Karp, R. M. (1993). Mapping the genome: some combinatorial problems arising in molecular biology. In STOC ’93: Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, pages 278–285, New York. ACM.

Lin, Y.-L. (2002). Triangle graphs and simple trapezoid graphs. Journal of Information Science and Engineering, 18(3):467–473.

Oliveira, F. d. S. (2006). Caracterizações de grafos de interseção de triângulos. Master’s thesis, COPPE/Universidade Federal do Rio de Janeiro, Brasil.

Papadimitriou, C. H. and Yannakakis, M. (1979). Scheduling interval-ordered tasks. SIAM Journal on Computing, 8(3):405–409.

Pe’er, I. and Shamir, R. (1997). Realizing interval graphs with size and distance constraints. SIAM Journal on Discrete Mathematics, 10(4):662–687.

Roberts, F. (1976). DiscreteMathematicalModels with Applications to Social, Biological, and Environmental Problems. Prentice Hall.

Spinrad, J. P. (2003). Efficient Graph Representations, volume 19 of Fields Institute Monographs. American Mathematical Society.