Boolean dimension and dim-boundedness: Planar cover graph with a zero

In 1989, Nešetřil and Pudlák 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 10. As a consequence, we are able to show that there is a reachability labeling scheme with labels consisting of O ( log ⁡ n ) bits for planar digraphs having a vertex from which every vertex is reachable. The best known scheme for general planar digraphs uses labels with O ( log 2 ⁡ n ) bits (Thorup, 2004 [16] , and it remains open to determine whether a scheme using labels with 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.