Caracterizações de Grafos de Interseção de Triângulos
Resumo
Um grafo é um grafo PI se é o grafo de interseção de uma família de triângulos entre duas retas paralelas. O problema do reconhecimento da classe dos grafos PI está em aberto há 20 anos. Apresentamos um estudo desta classe enfocando aspectos estruturais e computacionais, visando a sua solução. Como principais resultados, relacionamos os grafos PI ao estudo de dimensão de ordens e mostramos que uma dimensão especial definida é um invariante de comparabilidade, resultado mais forte que o análogo para a bem conhecida dimensão intervalar. Formulamos também uma conjectura que se verdadeira implica no reconhecimento eficiente dos grafos PI. Analisamos esta conjectura de forma teórica e computacional, apontando evidências para sua veracidade.Referências
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.
Publicado
30/06/2007
Como Citar
CERIOLI, Márcia R.; OLIVEIRA, Fabiano de S.; SZWARCFITER, Jayme L..
Caracterizações de Grafos de Interseção de Triângulos. In: CONCURSO DE TESES E DISSERTAÇÕES (CTD), 20. , 2007, Rio de Janeiro/RJ.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2007
.
p. 2013-2017.
ISSN 2763-8820.
