On the structure of trapezoid graphs (Q1917308): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 06:14, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the structure of trapezoid graphs |
scientific article |
Statements
On the structure of trapezoid graphs (English)
0 references
7 July 1996
0 references
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.
0 references
intervals
0 references
trapezoid
0 references
intersection graph
0 references
trapezoid graph
0 references
permutation graphs
0 references
interval graphs
0 references
vertex splitting
0 references
algorithm
0 references