On the structure of trapezoid graphs (Q1917308): Difference between revisions

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 \textit{T.-H. Ma} and \textit{J. P. Spinrad} [Lect. Notes Comput. Sci. 484, 61-71 (1992; Zbl 0768.68162)], put conceptually simpler and easier to code.