On the Order Dimension of Outerplanar Maps

摘要

Schnyder characterized planar graphs in terms of order dimension. Bright-well and Trotter proved that the dimension of the vertex-edge-face poset P_M of a planar map M is at most four. In this paper we investigate cases where dim(P_w) < 3 and also where dim(Q_w) < 3; here Q_m denotes the vertex-face poset of M. We show: 1.If M contains a K_4-subdivision, then dim(P_M) = dim(Q_u) = 4. 2.If M or the dual M~* contains aK_2,3-subdivision, then dim(P_w) = 4. Hence, a map M with dim(P_M) < 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(P_w) < 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(Q_w) < 3. There are, however, outerplanar maps with = 4. We construct the first such example.