On the Representation of a PI-Graph

Authors

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

DOI:

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

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.

Downloads

Published

2007-06-01

How to Cite

Almeida, S., de Mello, C., & Gomide, A. (2007). On the Representation of a PI-Graph. Trends in Computational and Applied Mathematics, 8(1), 1–10. https://doi.org/10.5540/tema.2007.08.01.0001

Issue

Vol. 8 No. 1 (2007)

Section

Original Article

License

Authors who publish in this journal agree to the following terms: 

  1. Authors retain copyright and grant the journal the right of first publication, with the work simultaneously licensed under the Creative Commons Attribution License that allows the sharing of the work with acknowledgment of authorship and initial publication in this journal.

  2. Authors are authorized to assume additional contracts separately, for non-exclusive distribution of the version of the work published in this journal (eg, publish in an institutional repository or as a book chapter), with acknowledgment of authorship and initial publication in this journal.
     

  3. Authors are allowed and encouraged to publish and distribute their work online (eg, in institutional repositories or on their personal page) at any point before or during the editorial process, as this can generate productive changes as well as increase impact and the citation of the published work (See The effect of open access).

  4. This is an open access journal which means that all content is freely available without charge to the user or his/her institution. Users are allowed to read, download, copy, distribute, print, search, or link to the full texts of the articles, or use them for any other lawful purpose, without asking prior permission from the publisher or the
    author. This is in accordance with the BOAI definition of open access

 

Intellectual Property

All the contents of this journal, except where otherwise noted, is licensed under a Creative Commons Attribution License under attribution BY.