In 1989, Ne\v{s}et\v{r}il and Pudl\'ak posed the following challenging question: Do planar posets have bounded Boolean dimension? We show that every poset with a planar cover graph and a unique minimal element has Boolean dimension at most $13$. As a consequence, we are able to show that there is a reachability labeling scheme with labels consisting of $\mathcal{O}(\log n)$ bits for planar digraphs with a single source. The best known scheme for general planar digraphs uses labels with $\mathcal{O}(\log^2 n)$ bits [Thorup JACM 2004], and it remains open to determine whether a scheme using labels with $\mathcal{O}(\log n)$ bits exists. The Boolean dimension result is proved in tandem with a second result showing that the dimension of a poset with a planar cover graph and a unique minimal element is bounded by a linear function of its standard example number. However, one of the major challenges in dimension theory is to determine whether dimension is bounded in terms of standard example number for all posets with planar cover graphs.
翻译:1989年, Ne\ v{s} et\ v{r}il 和 Pudl\'ak 提出了以下具有挑战性的问题: 平面图状图状图状的尺寸与布尔的维度相联吗? 我们显示, 每一个带有平面覆盖图和独特最小元素的图状都有布尔的维度, 最多为 $13 美元。 因此, 我们能够显示, 有一个由 $\ mathcal{O} (\log n) 和 Pudl\'ak 组成的标签标签可达标性标签方案。 一般平面图的已知比特(log2 n) 使用 $\ mathcal{O} (log\log n) 的标签方案。 (log n) 和第二个结果显示, 一般平面图状图状图和独特最小元素的尺寸由其标准示例编号的线性函数所约束。 然而, 一个带有 $\ mas main screal screstrical sium situal situal situde 在标准图状图状图状中确定所有标准的维度的挑战。