On the Representation of a PI-Graph
DOI:
https://doi.org/10.5540/tema.2007.08.01.0001Resumo
Consider two parallel lines (denoted r1 and r2). A graph is a PI graph (Point-Interval graph) if it is an intersection graph of a family F of triangles between r1 and r2 such that each triangle has an interval with two endpoints on r1 and a vertex (a point) on r2. The family F is the PI representation of G. The PI graphs are an extension of interval and permutation graphs and they form a subclass of trapezoid graphs. In this paper, we characterize the PI graphs in terms of its trapezoid representation. Also we show how to construct a family of trapezoid graphs but not PI graphs from a trapezoid representation of a known graph in this class.Referências
[1] K.S. Booth, G.S. Lueker, Testing for the consecutive ones property, interval graphs, and planarity using PQ-tree algorithms, J. Comput. System Sci., 13 (1976), 335-379.
A. Brandst¨adt, V. Le, J. Spinrad, “Graph Classes - a Survey”, SIAM, Monographs on Discrete Mathematics and Applications, 1999.
F. Cheah, “A Recognition Algorithm for II-Graphs”, Doctoral Thesis, TR246/90, Dept. of Computer Science, Univ. of Toronto, 1990.
F. Cheah, D.G. Corneil, On the structure of trapezoid graphs, Discrete Appied Mathematics, 66 (1996), 109-133.
O. Cogis, On the Ferrers dimension of a digraph, Discrete Math., 38 (1982), 47-52.
D.J. Corneil, P.A. Kamula. Extensions of permutation and interval graphs, Congressus Numerantium, 58 (1987), 267–275.
S. Even, A. Pnueli, A. Lempel, Permutation graphs and transitive graphs, J. ACM., 19 (1972), 400-410.
S. Felsner. Tolerance graphs and orders, Lecture Notes in Computer Science 657 (1992), 17–26.
M.C. Golumbic, “Algorithmic Graph Theory and Perfect Graphs”, Academic Press, New York, 1980.
M. Habib, R.H. M¨ohring, “Recognition of Partial Orders with Interval Dimension Two Via Transitive Orientation with Side Constrains”, Technical Report, TR 244/90, Tu Berlin, 1990.
M. Habib, R. McConnell, C. Paul, L. Viennot, Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing, Theoretical Computer Science, 234 (2000), 59-84.
G. Haj´os, ¨ Uber eine art von graphen, Internat. Math. Nachr., 11 (1957), problem 65.
N. Korte, H. M¨ohring, An incremental linear-time algorithm for recognizing interval graphs, SIAM J. Comput., 18 (1989), 68-81.
Y-L Lin, Triangle graphs and simple trapezoid graphs, Journal of Information Science and Engineering, 18 (2002), 467-473.
T.H. Ma, “Algorithms on Special Classes of Graphs and Partially Ordered Sets”, Ph.D. Thesis, Dept. of Computer Science, Vanderbilt Univ., Nashville, TN, 1990.
A. Pnueli, A. Lempel, S. Even, Transitive orientation of graphs and identification of permutation graphs, Canad. J. Math., 23 (1971), 160-175.
Downloads
Publicado
Como Citar
Edição
Seção
Licença
Direitos Autorais
Autores de artigos publicados no periódico Trends in Computational and Applied Mathematics mantêm os direitos autorais de seus trabalhos. O periódico utiliza a Atribuição Creative Commons (CC-BY) nos artigos publicados. Os autores concedem ao periódico o direito de primeira publicação.
Propriedade Intelectual e Termos de uso
O conteúdo dos artigos é de responsabilidade exclusiva dos autores. O periódico utiliza a Atribuição Creative Commons (CC-BY) nos artigos publicados. Esta licença permite que os artigos publicados sejam reutilizados sem permissão para qualquer finalidade, desde que o trabalho original seja corretamente citado.
O periódico encoraja os Autores a autoarquivar seus manuscritos aceitos, publicando-os em blogs pessoais, repositórios institucionais e mídias sociais acadêmicas, bem como postando-os em suas mídias sociais pessoais, desde que seja incluída a citação completa à versão do website da revista.
