On the structure of trapezoid graphs

DOI10.1016/0166-218X(94)00158-AzbMath0849.05060WikidataQ128109596 ScholiaQ128109596MaRDI QIDQ1917308

F. Cheah, Derek Gordon Corneil

Publication date: 7 July 1996

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

intervalstrapezoidalgorithmintersection graphtrapezoid graphinterval graphspermutation graphsvertex splitting

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (05C99)

Related Items (8)

Max-min weight balanced connected partition ⋮ Recognizing simple-triangle graphs by restricted 2-chain subgraph cover ⋮ A recognition algorithm for simple-triangle graphs ⋮ Efficient algorithm for the vertex connectivity of trapezoid graphs ⋮ An efficient algorithm to solve the conditional covering problem on trapezoid graphs ⋮ Vertex splitting and the recognition of trapezoid graphs ⋮ An efficient algorithm to generate all maximal independent sets on trapezoid graphs ⋮ An Efficient Algorithm to Generate all Maximal Cliques on Trapezoid Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of regular subgraph recognition
• On realizable biorders and the biorder dimension of a relation
• On some complexity properties of N-free posets and posets with bounded decomposition diameter
• Trapezoid graphs and their coloring
• On the Ferrers dimension of a digraph
• On Comparability and Permutation Graphs

This page was built for publication: On the structure of trapezoid graphs