On the order dimension of outerplanar maps (Q651434): Difference between revisions

This paper examines the relation between a planar map \(M\) and the order dimension of some related posets. The dimension \(\dim(P)\) of a poset \(P\) is the minimum \(t\) such that \(P\) is the intersection of \(t\) linear orders. The posets considered are the vertex-edge-face poset \(P_M\) where the elements are ordered by inclusion, and the vertex-face poset \(Q_M\) defined similarly. The authors show that if \(M\) contains a subdivision of \(K_4\), then \(\dim(P_M) = \dim(Q_M)=4\), and that if either \(M\) or its dual \(M^*\) contains a subdivision of \(K_{2,3}\), then \(\dim(P_M)= 4\). Hence if \(\dim(P_M) \leq 3\), then both \(M\) and \(M^*\) is outerplanar. They examine this case and show that \(\dim(P_M) \leq 3\) is equivalent to the existence of a certain oriented coloring of the edges, yielding a linear-time algorithm for verification. Finally, they show if if \(M\) is 2-connected and both \(M,M^*\) are outerplanar, then \(\dim(Q_M)\leq 3\). They also give an outerplanar map with \(\dim(Q_M) = 4\).