On the Representation of a PI-Graph

S.M. Almeida, C.P. de Mello, A. Gomide

Abstract


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.

References


[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.




DOI: https://doi.org/10.5540/tema.2007.08.01.0001

Article Metrics

Metrics Loading ...

Metrics powered by PLOS ALM

Refbacks

  • There are currently no refbacks.


Trends in Computational and Applied Mathematics

A publication of the Brazilian Society of Applied and Computational Mathematics (SBMAC)

 

Indexed in:

                       

         

 

Desenvolvido por:

Logomarca da Lepidus Tecnologia