On the structure of trapezoid graphs (Q1917308): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: Q791541 / rank | |||
Property / author | |||
Property / author: Derek Gordon Corneil / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3941433 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5422499 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The complexity of regular subgraph recognition / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the Ferrers dimension of a digraph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3797233 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Trapezoid graphs and their coloring / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On realizable biorders and the biorder dimension of a relation / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3328583 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On some complexity properties of N-free posets and posets with bounded decomposition diameter / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4028102 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On Comparability and Permutation Graphs / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Revision as of 13:09, 24 May 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