Language:   Search:   Contact
Zentralblatt MATH has released its new interface!
For an improved author identification, see the new author database of ZBMATH.

Query:
Fill in the form and click »Search«...
Format:
Display: entries per page entries
Zbl 0849.05060
Cheah, F.; Corneil, D.G.
On the structure of trapezoid graphs.
(English)
[J] Discrete Appl. Math. 66, No.2, 109-133 (1996). ISSN 0166-218X

Consider two parallel lines each containing $n$ intervals, labelled 1 to $n$, where two intervals with the same label define a trapezoid with that label. The intersection graph of such a set of trapezoids is called a trapezoid graph. Trapezoid graphs contain both permutation graphs and interval graphs. The paper deals with an operation called vertex splitting which allows to transform a trapezoid graph into a permutation graph with special properties. This implies an $O(n^3)$ algorithm for recognizing a trapezoid graph. The algorithm is slower than Ma's algorithm, see {\it T.-H. Ma} and {\it J. P. Spinrad} [Lect. Notes Comput. Sci. 484, 61-71 (1992; Zbl 0768.68162)], put conceptually simpler and easier to code.
[G.Gutin (Odense)]
MSC 2000:
*05C85 Graphic algorithms
05C99 Graph theory

Keywords: intervals; trapezoid; intersection graph; trapezoid graph; permutation graphs; interval graphs; vertex splitting; algorithm

Citations: Zbl 0768.68162

Cited in: Zbl 1223.05301

Highlights
Master Server