The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial

DOI10.1137/140963108zbMath1317.05132OpenAlexW2408404065MaRDI QIDQ5499731

George B. Mertzios

Publication date: 31 July 2015

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: http://dro.dur.ac.uk/15767/1/15767.pdf

zbMATH Keywords

intersection graphpolynomial algorithmpartial orderrecognition problemPI graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Combinatorics of partially ordered sets (06A07) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (4)

A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs ⋮ Recognizing simple-triangle graphs by restricted 2-chain subgraph cover ⋮ A recognition algorithm for simple-triangle graphs ⋮ A vertex ordering characterization of simple-triangle graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The recognition of triangle graphs
• Trapezoid graphs and their coloring
• Proper and unit bitolerance orders and graphs
• Triangulating multitolerance graphs
• Efficient graph representations
• Algorithmic graph theory and perfect graphs
• Threshold graphs and related topics
• An intersection model for multitolerance graphs: efficient algorithms and hierarchy
• The Recognition of Tolerance and Bounded Tolerance Graphs
• Linear-Interval Dimension and PI Orders
• Max-tolerance graphs as intersection graphs
• The Complexity of the Partial Order Dimension Problem
• Sufficient Conditions for Graphs to Have Threshold Number 2
• On the Complexity of Timetable and Multicommodity Flow Problems
• Graph Classes: A Survey
• On the 2-Chain Subgraph Cover and Related Problems
• Threshold Numbers and Threshold Completions

This page was built for publication: The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial