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

DOI10.1137/140963108MaRDI QIDQ5499731zbMATH OpenOpenAlexFDO

Authors 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

partial orderintersection graphrecognition problempolynomial algorithmPI graph

Mathematics Subject Classification ID

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

Recommendations

• The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders Is Polynomial
• A vertex ordering characterization of simple-triangle graphs
• A recognition algorithm for simple-triangle graphs
• The interval order polytope of a digraph
• Polygonal graphs as ordered sets: the Sperner criterion
• Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete
• Linear recognition of almost interval graphs
• The recognition of triangle graphs
• The recognition of triangle graphs
• Recognition of some perfectly orderable graph classes

Cites work

• scientific article; zbMATH DE number 4063148 (Why is no real title available?)
• scientific article; zbMATH DE number 1263242 (Why is no real title available?)
• scientific article; zbMATH DE number 2117210 (Why is no real title available?)
• Algorithmic graph theory and perfect graphs
• An intersection model for multitolerance graphs: efficient algorithms and hierarchy
• Efficient graph representations
• Graph Classes: A Survey
• Linear-Interval Dimension and PI Orders
• Max-tolerance graphs as intersection graphs
• On the 2-Chain Subgraph Cover and Related Problems
• On the Complexity of Timetable and Multicommodity Flow Problems
• Proper and unit bitolerance orders and graphs
• Sufficient Conditions for Graphs to Have Threshold Number 2
• The Complexity of the Partial Order Dimension Problem
• The recognition of tolerance and bounded tolerance graphs
• The recognition of triangle graphs
• Threshold Numbers and Threshold Completions
• Threshold graphs and related topics
• Trapezoid graphs and their coloring
• Triangulating multitolerance graphs

Cited in

(11)

• Linear-Interval Dimension and PI Orders
• Graph classes equivalent to 12-representable graphs
• A recognition algorithm for simple-triangle graphs
• The complexity of transitively orienting temporal graphs
• The recognition of triangle graphs
• Forbidden pattern characterizations of 12-representable graphs defined by pattern-avoiding words
• A vertex ordering characterization of simple-triangle graphs
• Ordering without forbidden patterns
• A linear-time algorithm for maximum-cardinality matching on cocomparability graphs
• The recognition of triangle graphs
• The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders Is Polynomial

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5499731)