Characterizations of Triangle Intersection Graphs
Abstract
A graph is a PI graph if it is the intersection graph of a family of triangles between two parallel lines. The recognition problem for the class of PI graphs has been open for 20 years. We present a study on such a class focusing on structural and computational aspects, in order to solve it. As main results, we relate PI graphs to the study of order dimensions and show that a particular defined dimension is a comparability invariant, a stronger result than the similar for the well-known interval dimension. Moreover, we formulate a conjecture which if it is true, then the recognition of PI graphs can be done efficiently. We theoretical and computationally analyze such a conjecture.References
Booth, K. S. and Lueker, G. S. (1976). Testing the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. Journal Comput. System Sci., pages 335–379.
Brandstädt, A., Le, V. B., and Spinrad, J. P. (1999). Graph Classes: a Survey. SIAM, Philadelphia.
Cheah, F. H. K. (1991). A Recognition Algorithm for II-graphs. PhD thesis, University of Toronto, Canada.
Corneil, D. G. and Kamula, P. K. (1987). Extensions of permutation and interval graphs. In 18th Southeastem Conference on Combinatorics. Graph Theory and Computing.
de Almeida, S. M. (2005). Grafos PI. Master’s thesis, Universidade Estadual de Campinas, Campinas, Brasil.
Felsner, S., Habib, M., and Möhring, R. (1994). On the interplay between interval dimension and ordinary dimension. SIAM Journal of Discrete Mathematics, 7:32–40.
Golumbic, M. C. (1980). Algorithmic Graph Theory and Perfect Graphs. San Diego, Academic Press.
Langley, L. (1995). Recognition of orders of interval dimension 2. Discrete Applied Mathematics, 60:257–266.
Lin, Y.-L. (2002). Triangle graphs and simple trapezoid graphs. J. Inf. Sci. Eng., 18(3):467–473.
Oliveira, F. S. (2006). Caracterizações de grafos de interseção de triângulos. Master’s thesis, COPPE/Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brazil.
Spinrad, J. P. (2003). Efficient Graph Representations, volume 19 of Fields Institute Monographs. AMS.
Trotter, W. T. (1992). Combinatorics and Partially Ordered Sets. The Johns Hopkins University Press, Baltimore and London.
Brandstädt, A., Le, V. B., and Spinrad, J. P. (1999). Graph Classes: a Survey. SIAM, Philadelphia.
Cheah, F. H. K. (1991). A Recognition Algorithm for II-graphs. PhD thesis, University of Toronto, Canada.
Corneil, D. G. and Kamula, P. K. (1987). Extensions of permutation and interval graphs. In 18th Southeastem Conference on Combinatorics. Graph Theory and Computing.
de Almeida, S. M. (2005). Grafos PI. Master’s thesis, Universidade Estadual de Campinas, Campinas, Brasil.
Felsner, S., Habib, M., and Möhring, R. (1994). On the interplay between interval dimension and ordinary dimension. SIAM Journal of Discrete Mathematics, 7:32–40.
Golumbic, M. C. (1980). Algorithmic Graph Theory and Perfect Graphs. San Diego, Academic Press.
Langley, L. (1995). Recognition of orders of interval dimension 2. Discrete Applied Mathematics, 60:257–266.
Lin, Y.-L. (2002). Triangle graphs and simple trapezoid graphs. J. Inf. Sci. Eng., 18(3):467–473.
Oliveira, F. S. (2006). Caracterizações de grafos de interseção de triângulos. Master’s thesis, COPPE/Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brazil.
Spinrad, J. P. (2003). Efficient Graph Representations, volume 19 of Fields Institute Monographs. AMS.
Trotter, W. T. (1992). Combinatorics and Partially Ordered Sets. The Johns Hopkins University Press, Baltimore and London.
Published
2007-06-30
How to Cite
CERIOLI, Márcia R.; OLIVEIRA, Fabiano de S.; SZWARCFITER, Jayme L..
Characterizations of Triangle Intersection Graphs. In: THESIS AND DISSERTATION CONTEST (CTD), 20. , 2007, Rio de Janeiro/RJ.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2007
.
p. 2013-2017.
ISSN 2763-8820.
