On the structure of trapezoid graphs

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

F. Cheah, Derek Gordon Corneil

Publication date: 7 July 1996

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

zbMATH Keywords

intervals; trapezoid; algorithm; intersection graph; trapezoid graph; interval graphs; permutation graphs; vertex splitting

Mathematics Subject Classification ID

05C85: Graph algorithms (graph-theoretic aspects)

05C99: Graph theory

Related Items

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

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item