Consider two parallel lines each containing
intervals, labelled 1 to
, 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
algorithm for recognizing a trapezoid graph. The algorithm is slower than Ma’s algorithm, see T.-H. Ma
and J. P. Spinrad
[Lect. Notes Comput. Sci. 484, 61-71 (1992; Zbl 0768.68162
)], put conceptually simpler and easier to code.