Advanced Search

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

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]