The Order Dimension of Planar Maps Revisited
Stefan Felsner · SIAM Journal on Discrete Mathematics · 2014
Schnyder characterized planar graphs in terms of order dimension. The structures used for the proof have found many applications. Researchers also found several extensions of the seminal result. A particularly far-reaching extension is the Brightwell--Trotter theorem about planar maps. It states that the order dimension of the incidence poset $\mathbf{P}_{\mathbf{M}}$ of vertices, edges, and faces of a planar map $\mathbf{M}$ has dimension at most 4. The original proof generalizes the machinery of Schnyder paths and Schnyder regions. In this short paper we use a simple result about the order dimension of grid intersection graphs to show a slightly stronger result: $\dim(\mathsf{split}(\mathbf{P}_{\mathbf{M}})) \leq 4$. Here, $\mathsf{split}(P)$ refers to a particular order of height two associated with $P$. The Brightwell--Trotter theorem follows because $\dim(\mathsf{split}(P)) \geq \dim(P)$ holds for every $P$. This may be the first result in the area that is obtained without using the tools introduced by Schnyder.