The Complexity of the Partial Order Dimension Problem: Closing the Gap

DOI10.1137/15M1007720zbMath1360.06001arXiv1501.01147OpenAlexW2963499318MaRDI QIDQ2957691

Stefan Felsner, Martin Pergel, Irina Mustaţă

Publication date: 27 January 2017

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

Full work available at URL: https://arxiv.org/abs/1501.01147

zbMATH Keywords

intersection graphNP-completenesstriangle containment

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Partial orders, general (06A06) Combinatorics of partially ordered sets (06A07) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

Sublinear approximation algorithms for boxicity and related problems ⋮ Grid intersection graphs and order dimension

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the order dimension of outerplanar maps
• Schnyder woods and orthogonal surfaces
• Planar graphs and poset dimension
• A special planar satisfiability problem and a consequence of its NP- completeness
• Intersection graphs of segments
• On the fractional dimension of partially ordered sets
• Geodesic embeddings and planar graphs
• Planar graphs as minimal resolutions of trivariate monomial ideals
• Fractional dimension of partial orders
• Computing the dimension of N-free ordered sets is NP-complete
• The Hardness of Approximating Poset Dimension
• The Complexity of the Partial Order Dimension Problem
• Planar Formulae and Their Uses
• The Order Dimension of Convex Polytopes
• Polynomial Time and Parameterized Approximation Algorithms for Boxicity
• Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation
• Permutation Graphs and Transitive Graphs
• Partially Ordered Sets