Planar Poset Dimension Gets a Linear Obstruction Bound

Computing the dimension of a partially ordered set is hard in general, and the complexity status for posets whose Hasse diagram is planar is still unresolved. This paper attacks the planar case from a different angle: it asks whether the canonical obstruction to small dimension, the standard example, controls dimension up to a bounded factor. For planar diagrams, the authors prove that it does, with an explicit linear bound.

The result is both structural and algorithmic. If $\mathrm{se}(P)$ is the maximum order of a standard example contained in a poset $P$, then every poset with a planar diagram satisfies

Since every standard example of order $k$ forces dimension at least $k$, this turns standard-example size into a constant-factor certificate for planar poset dimension.

Core Contribution

The main contribution is a sharper version of a bound proved in the first paper of the series. The earlier result handled the broader class of posets with planar cover graphs and obtained a polynomial dependence on $\mathrm{se}(P)$. Here the authors work in the original setting of planar diagrams, where the drawing respects the order direction, and recover a linear dependence with explicit constants.

The paper’s proof is organized around reversible sets of incomparable pairs. By the classical Trotter-Moore characterization, a set of incomparable pairs is reversible exactly when it contains no alternating cycle; dimension is the least number of reversible sets needed to cover all incomparable pairs. The authors turn the planar drawing into a geometric control mechanism for those alternating cycles.

Technical Approach

The argument reduces the dimension problem to a more constrained covering problem. The paper introduces a “singly constrained planar diagram dimension” subproblem: a set $I$ of incomparable pairs is constrained by a fixed element $x_0$, and the goal is to cover $I$ by a bounded number of reversible sets unless a large standard example appears. Lemma 7 gives the algorithmic heart of the paper: for every positive integer $n$, there is an $f$-good polynomial-time algorithm for this subproblem with $f(n)=4n+24$.

Much of the technical machinery is topological. The authors fix a planar embedding and represent witness paths between comparable elements as vertically monotone curves. They define leftmost and rightmost witness paths, prove that these paths can be computed in polynomial time, and use consistency properties of these paths to impose partial orders on boundary elements. This is why the proof needs bottom-consistency, top-consistency, and extremal paths rather than a naive planar-order argument.

The later proof studies regions determined by right or left witness paths. For a right pair $(a,b)$, the construction selects auxiliary boundary elements such as $b'$ and $b''$, defines a minimal region $\mathcal{R}(a,b',b'')$, and proves containment relations between these regions. The point of this machinery is to show that if the algorithm fails to certify reversibility, the resulting strict alternating-cycle structure can be converted into a large standard example. That is the obstruction-to-dimension link.

Results and Analysis

The headline theorem gives the quantitative payoff: planar diagrams satisfy $\mathrm{dim}(P) \leq 96\mathrm{se}(P)+672$. This is a constant-factor relation between dimension and the largest standard example, because $\mathrm{se}(P) \leq \mathrm{dim}(P)$ always holds. The paper also states a polynomial-time approximation algorithm for computing dimension within this class, driven by the same reversible-set covering procedure.

The constants are not presented as optimized. They arise from repeated reductions: the singly constrained algorithm has the explicit bound $4n+24$, and the full proof combines multiple families of incomparable pairs and reversible-set covers. The value of the result is therefore not that 96 and 672 are small enough for direct implementation, but that the dependence is linear and constructive.

The evidence is a formal proof rather than experiments. The paper supplies algorithmic subroutines where needed, including a polynomial-time test for reversibility via an auxiliary directed graph whose cycles correspond to alternating cycles. It also relies on known equivalences for poset dimension: a realizer is a family of linear extensions, and dimension is the minimum number of reversible sets covering $\mathrm{Inc}(P)$.

Limits

The result does not settle whether exact dimension is polynomial-time computable for planar posets. It gives a constant-factor approximation and a structural bound tied to standard examples. The proof also depends on planar diagrams, not merely arbitrary drawings or non-planar cover graphs. Finally, the algorithm is constructive in a theoretical sense, but the paper’s large constants and long geometric case analysis leave open whether the method would be practical for computing small realizers on real instances.