{"id":"arxiv/2607.09294","url":"https://arxiv.org/abs/2607.09294","tags":["math.CO"],"score":0,"title":"Planarity and dimension II","domain":"math.CO","source":"arxiv","authors":["Heather S. Blake","Jędrzej Hodor","Piotr Micek","Michał T. Seweryn","William T. Trotter"],"reviews":0,"subject":"math.CO","summary":"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,…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-10","reactions":{}}