Open Research Index

Planarity and dimension II

Heather S. Blake, Jędrzej Hodor, Piotr Micek, Michał T. Seweryn, William T. Trotter

arXivarxiv/2607.09294Jul 10, 2026math.COscore 0

The dimension of a poset $P$ is the minimum positive integer $d$ such that $P$ is an induced subposet of $\mathbb{R}^d$ equipped with the product order. We give a constant-factor polynomial-time approximation algorithm for computing dimension in the class of posets with a planar (Hasse) diagram. While computing the dimension of a poset is NP-hard in general, the computational complexity of the problem for planar posets remains open. The algorithmic result is driven by a structural understanding of the canonical obstruction to small dimension: standard examples. A longstanding problem,…

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2607.09294
curl -X POST /api/v1/records/arxiv/2607.09294/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.09294/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'