On the structure of trapezoid graphs
type: Item
instance of: scholarly article
title: On the structure of trapezoid graphs
zbMATH Open document ID: 0849.05060
DOI: 10.1016/0166-218X(94)00158-A
author: F. Cheah
author: Derek G. Corneil
published in: Discrete Applied Mathematics
publication date: 1996-07-07T00:00:00Z
review text: 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.
reviewed by: G. Gutin
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 897408
zbMATH Keywords: intervals
zbMATH Keywords: trapezoid
zbMATH Keywords: intersection graph
zbMATH Keywords: trapezoid graph
zbMATH Keywords: permutation graphs
zbMATH Keywords: interval graphs
zbMATH Keywords: vertex splitting
zbMATH Keywords: algorithm
MaRDI profile type: Publication
cites work: Q3941433
cites work: Q5422499
cites work: The complexity of regular subgraph recognition
cites work: On the Ferrers dimension of a digraph
cites work: Q3797233
cites work: Trapezoid graphs and their coloring
cites work: On realizable biorders and the biorder dimension of a relation
cites work: Q3328583
cites work: On some complexity properties of N-free posets and posets with bounded decomposition diameter
cites work: Q4028102
cites work: On Comparability and Permutation Graphs
Wikidata QID: Q128109596
Recommended article: Trapezoid graphs and generalizations, geometry and algorithms
Recommended article: Dominations in trapezoid graphs
Recommended article: Trapezoid graphs and their coloring
Recommended article: Complexity of trapezoidal graphs with different triangulations
Recommended article: Vertex splitting and the recognition of trapezoid graphs
Recommended article: Extending partial representations of trapezoid graphs
Recommended article: On powers of \(m\)-trapezoid graphs
Recommended article: Q4267317
Recommended article: Q3828039
description: scientific article; zbMATH DE number 897408