On the structure of trapezoid graphs (Q1917308): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Created claim: Wikidata QID (P12): Q128109596, #quickstatements; #temporary_batch_1722371031483 |
||
Property / Wikidata QID | |||
Property / Wikidata QID: Q128109596 / rank | |||
Normal rank |
Latest revision as of 22:28, 30 July 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
0 references