On the Order Dimension of Outerplanar Maps

Stefan Felsner, Johan Nilsson

Published 2009-06-02Version 1

Schnyder characterized planar graphs in terms of order dimension. Brightwell and Trotter proved that the dimension of the vertex-edge-face poset $\Pvef{M}$ of a planar map $M$ is at most four. In this paper we investigate cases where $\dim(\Pvef{M}) \leq 3$ and also where $\dim(\Qvf{M}) \leq 3$; here $\Qvf{M}$ denotes the vertex-face poset of $M$. We show: - If $M$ contains a $K_4$-subdivision, then $\dim(\Pvef{M}) = \dim(\Qvf{M}) = 4$. - If $M$ or the dual $M^*$ contains a $K_{2,3}$-subdivision, then $\dim(\Pvef{M}) = 4$. Hence, a map $M$ with $\dim(\Pvef{M}) \leq 3$ must be outerplanar and have an outerplanar dual. We concentrate on the simplest class of such maps and prove that within this class $\dim(\Pvef{M}) \leq 3$ is equivalent to the existence of a certain oriented coloring of edges. This condition is easily checked and can be turned into a linear time algorithm returning a 3-realizer. Additionally, we prove that if $M$ is 2-connected and $M$ and $M^*$ are outerplanar, then $\dim(\Qvf{M}) \leq 3$. There are, however, outerplanar maps with $\dim(\Qvf{M}) = 4$. We construct the first such example.